BOJ 21768 - AND PLUS OR (Python3)

굉장히 오랜만에 블로그에 글을 쓰는 느낌이다. 대학원생이 된 이후로 바빠서 문제를 풀더라도 블로그에 글을 쓸 시간이 안 났다. 짬이 생긴 터라 오늘 푼 문제의 풀이를 작성한다.

이 문제를 품으로서 수학 태그레이팅이 2600에 도달했다. 2700까지 올리고는 싶으나 아직 내가 그럴 만한 체급이 안 되는 것 같기도 하다. 천천히 올리자. 급하게 하지 말고.

---

문제

두 음이 아닌 정수 $a,b$에 대하여 $a\wedge b,a\vee b$는 각각 이들의 bitwise AND, bitwise OR를 나타낸다.

음이 아닌 정수로 구성된 길이 $2^N$의 정수열 $A_0,A_1,\cdots ,A_{2^N-1}$에 대해 $A_i+A_j<A_{i\wedge j}+A_{i\vee j}$를 만족하는 $0\le i,j<2^N$이 존재하는지 판별하고, 만약 존재한다면 $i,j$를 아무거나 하나 출력하라.

 

입력

첫째 줄에 음이 아닌 정수 $N$이 주어진다. $(0\le N\le 20)$

둘째 줄에 정수열의 원소를 나타내는 $2^N$개의 음이 아닌 정수가 공백으로 구분되어 주어진다. 순서대로 $A_0,A_1,\cdots ,A_{2^N-1}$을 의미한다. $(0\le A_i\le {10}^7)$

 

예제 입력)

# 예제 1
2
0 1 1 2

# 예제 2
2
0 1 1 3

 

출력

만약 문제의 조건을 만족하는 $i,j$가 있으면 이를 공백으로 구분하여 출력한다. 그렇지 않다면 대신 $-1$을 출력한다.

 

예제 출력)

# 예제 1
-1

# 예제 2
1 2

 

---

내 코드

N,*a = map(int,open(0).read().split())
for mask in range(1<<N):
    for i in range(N-1):
        for j in range(i+1,N):
            if 0 == mask & (1<<i):
                if 0 == mask & (1<<j):
                    I,J = mask+(1<<i),mask+(1<<j)
                    iorj = I+J-mask
                    if a[I]+a[J] < a[mask]+a[iorj]:
                        print(I,J); exit(0)
print(-1)

 

매우 풀이가 아름다운데, 그에 비해 구현량은 무시할 수 있을 정도로 짧다. 누군가는 마음에 안 들어하는 유형의 문제겠지만 나는 매우 좋다. 이런 문제가 더 많아졌으면 좋겠다.

$i,j$를 $i=x\vee y,j=x\vee z$로 둔다. 여기서 $x,y,z$는 그 어느 두 개를 뽑아도 bitwise AND값이 0인 세 정수이다. 그러면 $A_i-A_{i\wedge j}<A_{i\vee j}-A_j$는 $A_{x\vee y}-A_x<A_{x\vee y\vee z}-A_{x\vee z}$와 같은 말이다.

$y$를 고정하자. 함수 $f_y(x)=A_{x\vee y}-A_x$를 생각하면 위 등식은 $f_y(x)<f_y(x\vee z)$임과 같은 소리이다. $z=\sum _1^k{2}^{a_i}$이면, $f_y(x\vee z)-f_y(x)=\sum _{i=1}^k(f_y(x\vee \sum _{j=1}^i{2}^{a_j})-f_y(x\vee \sum _{j=1}^{i-1}{2}^{a_j}))>0$이므로 적어도 하나의 $f_y(x\vee \sum _{j=1}^i{2}^{a_j})-f_y(x\vee \sum _{j=1}^{i-1}{2}^{a_j})$는 0보다 크다. 따라서 문제의 조건을 만족시키는 $(x,y,z)$가 주어진다면, $z=2^i$ 꼴의 해도 하나 존재한다.

이 $z=2^i$꼴의 해를 고정해놓고 똑같이 위 풀이를 반복하면, $y=2^i,z=2^j$ 꼴의 해가 존재함 역시 보일 수 있다. 이러면 $2^N$개의 모든 $x$에 대하여, 각각 최대 $N$개의 $y,z$가 존재하므로 완전탐색을 할 수 있다. 시간복잡도는 $\mathcal{O}(N^2{2}^N)$이고, $N=20$이므로 여유롭게 통과한다.

 

이로서 21768번의 풀이를 마친다.