2226 이진수

https://www.acmicpc.net/problem/2226

2226번: 이진수

---

문제에서 말하는 대로 처음 몇 개의 이진수들을 구해보면 아래처럼 나오게 된다.

0 x
1 1
2 01
3 1001
4 01101001
5 1001011001101001
6 01101001100101101001011001101001
7 1001011001101001011010011001011001101001100101101001011001101001
...

dp는 이전에 구했었던 결과를 이용한다는 점을 생각해보면 반복되는 패턴이 있음을 발견할 수 있었다.

 

5번째 패턴은 1001011001101001이고 6번째 패턴은 01101001100101101001011001101001인데, 6번째 패턴을 절반으로 자른 후 뒷부분을 보면 5번째 패턴과 똑같다.

 

4번째 패턴을 보면 01101001이 5번째 패턴을 의미하는데, 5번째 패턴의 뒷부분이 01101001이기 때문이다.

 

이렇게, i번째 패턴의 절반의 뒷부분(?)은 i-1번째 패턴임을 알 수 있었다.

 

나머지 앞부분에서도 비슷한 모습인데, i번째 패턴은 i-2번째 패턴으로 시작하고 있다. 

 

6번째 패턴은 01101001100101101001011001101001인데 4번째 패턴은 01101001이다.

 

i-2번째 패턴 + ??? + i-1번째 패턴 = i번째 패턴

 

??? 위치에 들어가는 것은 i-1번째 패턴에 나와 있는데, i-1번째 패턴에서 i-2번째 패턴을 빼면 된다.

 

6번째 패턴의 ??? 부분은 10010110인데, 5번째 패턴에서 발견할 수 있다. 

 

5번째 패턴은 1001011001101001이다. 여기서 4번째 패턴은 01101001인데 5번째 패턴의 뒷부분이므로 이 뒷부분을 빼면 된다.

 

식을 정리하면,

i-2번째 패턴 + i-1번째 패턴 - i-2번째 패턴 + i-1번째 패턴 = i-1번째 패턴 + i-1번째 패턴

 

주의해야할 점은 0의 개수를 세는게 아니라 0의 그룹을 세는 것이다. 패턴의 모양을 만든 뒤 0의 그룹 개수를 세면 매우 시간이 걸리므로 각 패턴에서 얻은 그룹 개수를 다루어야 한다.

 

5번째 패턴의 개수를 세어볼 때를 살펴보면 4번째 패턴이 0으로 시작하고, 가운데 부분이 0으로 이어지고 있다. 4번째 패턴의 0의 그룹수는 3개인데, 5번째 패턴의 가운데 부분이 0으로 이어지므로 중복으로 센 부분은 제거해야한다. 

 

N이 홀수일 때) 직전 패턴 * 2 - 1

 

6번째 패턴의 개수를 세어볼 때를 살펴보면 5번째 패턴을 쪼갤 때 가운데에 있는 0의 그룹이 쪼개지는 것을 볼 수 있다. 

그러므로 1개였던 그룹이 2개로 쪼개졌기 때문에 1을 더해주어야 한다.

 

N이 짝수일 때) 직전 패턴 * 2 + 1

---

여기까지 점화식을 만들고 제출해보니 틀렸다고 나온다. 어째서인지 모든 답을 출력해보니 int의 범위를 넘어가더라.

 

직전 값의 배수에 1을 더한 값을 만드는 걸 생각해보면 당연하다. N의 범위도 1000까지 올라가기 때문에 큰 수를 다루는 자료형을 만들어야 한다.

 

보통 vector를 이용해서 만드는데, 나는 귀찮아서!!! 배열로 해버렸다. 덕분에 메모리 크기가 6mb를 찍었다. 이렇게 풀면 안되겠다.

 

#include <iostream>
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))

int dp[1001][1001]{0};
int len[1001]{1, 1, 1};

void decrease(int N) {
  dp[N][1]--;
  for (int i = 1; i <= len[N]; i++) {
    if (dp[N][i] < 0) {
      dp[N][i] += 10;
      dp[N][i + 1]--;
    } else {
      break;
    }
  }
}

void increase(int N) {
  dp[N][1]++;
  for (int i = 1; i <= len[N]; i++) {
    if (dp[N][i] >= 10) {
      dp[N][i] = 0;
      dp[N][i + 1]++;
    } else {
      break;
    }
  }
}

int main() {
  int N;
  dp[2][1] = 1;
  scanf("%d", &N);
  for (int i = 3; i <= N; i++) {
    int u = 0, d;
    len[i] = len[i - 1] + (dp[i - 1][len[i - 1]] > 4);
    for (int j = 1; j <= len[i]; j++) {
      d = dp[i - 1][j] * 2 + u;
      dp[i][j] = d % 10;
      u = d / 10;
    }
    if (i % 2) {
      decrease(i);
    } else {
      increase(i);
    }
  }
  for (int i = len[N]; i > 0; i--)
    printf("%d", dp[N][i]);
}

N이 1일땐 답이 0이다.