백준 이진수(2226)

이진수

1. 힌트

1) 수열의 가장 첫 자리는 $0$과 $1$을 교대로 반복하고, 마지막 자리는 무조건 $1$입니다.

2) 주어진 이진수를 가운데에서 나눠서 비교하면 서로 반전되어있다는 것을 알 수 있습니다.

3) 만약 $0$에서 시작해서 치환한다면 어떤 수열이 만들어지는지 확인해봅시다.

2. 접근

1) 수열의 특성 파악

수열은 재귀적으로 정의되었습니다. 대개 이런 경우 십중팔구 DP로 해결이 가능한데, 수열의 특성을 먼저 파악해 봅시다.

이진수의 길이는 $2$배씩 늘어납니다. $N$번째 원소의 길이는 $2^N$이므로 엄청나게 길이가 커질 것을 알 수 있습니다.

치환하는 연산은 $0$의 왼쪽에 $1$을 추가하고, $1$의 왼쪽에는 $0$을 추가하는 것으로 이해할 수 있습니다. 따라서 가장 첫 자리는 $0$과 $1$을 교대로 반복하고, 마지막 자리는 $1$로 고정됨을 알 수 있습니다.

$0$에서 시작해서 수열을 만들어 나간다면 어떨까요? 원래 수열이 $S$고 $0$에서 시작하는 수열을 $R$이라고 하면 다음과 같은 형태입니다.
$S = 1 \to 01 \to 1001 \to 01101001 \to ...$
$R = 0 \to 10 \to 0110 \to 10010110 \to ...$

2) 점화식 구성

$S_1 = 01$인데 여기서 왼쪽에 있는 $0$을 $R_0$이라고 생각할 수 있습니다. 이렇게 하면 수열을 재귀적으로 다음과 같이 표현할 수 있습니다.
$S_i = R_{i-1}S_{i-1}$
그런데 $R$을 관찰해 보니 $R$또한 이런 방식으로 표현할 수 있습니다.
$R_i = S_{i-1}R_{i-1}$

$S,\ R$에 대해서 연속된 $0$들의 그룹의 개수를 각각 함수 $f(i),\ g(i)$로 정의하면 다음과 같습니다.
$f(i) = f(i - 1) + g(i - 1) - 1$($i$가 홀수라면)
$g(i) = f(i - 1) + g(i - 1)$
$R$의 끝부분과 $S$의 첫 부분은 $0$과 $1$을 교대로 반복합니다. $i - 1$이 홀수라면 가운데에 맞닿는 부분이 $0$끼리 만나므로 $0$그룹의 개수를 하나 줄여줘야합니다.
$g(i)$는 $\displaystyle\sum_{k=0}^{i}f(k)$이므로 $O(N)$의 시간에 구할 수 있습니다. 다시 정리하면 $f(i) = f(i - 1) + \displaystyle\sum_{k=0}^{i-1}f(k) - 1$($i$가 홀수라면) 입니다.

3. 구현

DP배열을 구간 합 배열로 정의하면 $O(N)$의 시간동안 $\displaystyle\sum_{k=0}^{i-1}f(k)$를 구하지 않고 이전 값을 그대로 쓰면 됩니다. 물론 $N$범위가 작기 때문에 $O(N^2)$으로도 충분히 돌아갑니다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        BigInteger[] dp = new BigInteger[N + 1];
        dp[0] = new BigInteger("0");
        dp[1] = new BigInteger("0");
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1].multiply(BigInteger.TWO).add(BigInteger.ONE);
            if (i % 2 == 1) dp[i] = dp[i].subtract(BigInteger.ONE);
        }
        System.out.println(dp[N].subtract(dp[N - 1]));
    }

}