[BOJ 20662] Hop

문제: https://www.acmicpc.net/problem/20662

 

힌트 1:

모든 $i<j$에 대해 $x_i$가 $x_j$를 나누는 경우만 문제를 풀어봅시다. 이 풀이를 원래 문제로 확장할 수 있을까요?

힌트 2는 해당 문제의 풀이에 대한 힌트, 힌트 3은 원래 문제로 확장하는 것에 대한 힌트입니다.

힌트 2-1:

이 문제의 채점은 어떤 식으로 이루어질까요?

힌트 2-2:

동적계획법을 사용하면, 어떤 노드에서 끝나는 한 가지 색으로 이루어진 최대 길이를 알 수 있습니다. 즉, 각 노드의 값을 $(r, g, b)$ 로 표현할 수 있습니다. 우리가 찾으려는 값은 $r, g, b \le 3$이니 서로 다른 $(r, g, b)$ 쌍이 $64$개 있을 것입니다. 이 관찰을 이용해서 간선을 잘 그을 수 있을까요?

힌트 3-1:

$x_i$가 $x_j$를 나누면 $2x_i \le x_j$ 를 만족합니다.

풀이:

$2^{k_i} \le x_i < 2^{k_i-1}$ 이라고 해 봅시다. $i <j, k_i = k_j$ 인 경우 $2x_i > x_j$ 이므로 $x_i$는 $x_j$를 나누지 못합니다. 그렇기 때문에 우리는 같은 $k_i$ 끼리는 간선의 색을 고려할 필요가 없고 다른 $k_i$들끼리만 간선의 색을 고려하는 것으로 충분합니다. $0 \le k_i \le 59$ 이기 때문에, $N=60$인 완전그래프에서 문제를 풀면 됩니다.

이제, 힌트 2의 동적계획법 관찰을 사용합니다. $(r_1, g_1, b_1) \rightarrow (r_2, g_2, b_2)$의 간선 색을 생각해봅시다. 간선이 빨간색이면 $r_2 > r_1$, 초록색이면 $g_2 > g_1$, 파란색이면 $b_2 > b_1$을 만족해야합니다.

 

수가 증가하는 방향으로 간선을 긋는 것이 좋을 것 같으니, $0$부터 $N-1$까지의 수를 $4$진법으로 표현해봅시다. $r_2 \times 4^2 + g_2 \times 4^1 + b_2 \times 4^0 > r_1 \times 4^2 + g_1 \times 4^1 + b_1 \times 4^0$를 만족한다는 의미는, $r_2 > r_1$, $g_2 > g_1$, $b_2 > b_1$ 중 하나 이상을 만족한다는 의미입니다. 만족하는 색을 이용해서 간선을 그리면 간선의 할당에 따른 DP값이 올바르게 할당이 됩니다.

 

정리해보면 다음과 같습니다:

• $k_i = \left\lfloor\log_2 (x_i)\right\rfloor$
• $i$에서 $j$로는 $k_i \oplus k_j$의 가장 상위 비트가 $2^0, 2^1$이면 파란색, $2^2, 2^3$이면 빨간색, $2^4, 2^5$이면 초록색을 그려주면 됩니다.

코드: https://www.acmicpc.net/source/share/60dae46cf42849bbbc18ad185c9c3d88