BOJ 2698 인접한 비트의 개수(C++)

인접한 비트의 개수 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	186	131	103	72.028%

문제

0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.

s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn

위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.

수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.

예를 들어, n이 5이고, k가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.

11100, 01110, 00111, 10111, 11101, 11011

입력

첫째 줄에 테스트 케이스의 수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 숫자 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 숫자는 n이고, 두 번째 숫자는 k이다. n은 100을 넘지 않는다.

출력

각 테스트 케이스에 대해 인접한 비트의 개수가 k인 수열 S의 개수를 한 줄에 하나씩 출력한다. 이 값은 2147483647보다 작거나 같다.

예제 입력 

10
5 2
20 8
30 17
40 24
50 37
60 52
70 59
80 73
90 84
100 90

예제 출력 

6
63426
1861225
168212501
44874764
160916
22937308
99167
15476
23076518

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest F번

• 문제의 오타를 찾은 사람: 79brue
• 문제를 번역한 사람: baekjoon

링크

• ACM-ICPC Live Archive
• PKU Judge Online
• Sphere Online Judge
• HDU Online Judge

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <iostream> using namespace std;   int main() {     int bits[111][111][2]; // n , k 일 때 0으로 끝나는 수열, 1로 끝나는 수열 저장.     int T;     int n, k;     for (int i = 0; i < 111; ++i)         for (int j = 0; j < 111; ++j)             bits[i][j][0] = bits[i][j][1] = 0;     bits[1][0][0] = 1; bits[1][0][1] = 1; //n이 1일 경우 0, 1각 한 경우씩 (k = 0)     for (int i = 2; i < 111; ++i)     {         for (int j = 0; j < i; ++j) // j(k)만큼의 인접한 비트를 가지려면 최소 i(n)이 그보다 1만큼 커야 함.         {             //0으로 끝나는 경우의 수 -> 0 + 0 해도 되고(k는 일정) / 0 + 1 해도 된다(k는 일정)             bits[i][j][0] = bits[i - 1][j][0] + bits[i - 1][j][1];             //1로 끝나는 경우의 수를 구하기 위해서는 -> 마지막이 0인 경우에는 1이 올 수 있음 (첫 항)             //                                      -> 1로 끝나는 경우에는 1이 오게 되면 k(j)가 하나 늘어나게 되므로 k(j)가 하나 작고 1로 끝난 것에서 1을 추가해주면 됨.             bits[i][j][1] = bits[i - 1][j][0] + bits[i - 1][j - 1][1];           }     }       cin >> T;     for (int t = 0; t < T; ++t)     {         cin >> n >> k;         cout << bits[n][k][0] + bits[n][k][1] << endl;       }     return 0; }

엄청 헤메고 어려웠지만... 풀고나니 별거 아니다 싶기도 하고 어이가 없기도 한 문제..? 

이친수 문제도 그렇고 비트, 이진수 모두 0과 1로 이루어져 있고, 현재 상태의 문제를 풀기 위해 이전 상태의 값을 이용하려고 생각해보니(다이나믹 프로그래밍)

우선 배열을 만들게 되었고, 배열에 들어갈 만한 값을 생각해보니 먼저 떠오른 것은 n와 k였다.

그 외의 제약조건이 있다면 n(자릿수) 는 항상 k(인접한 비트 갯수)보다 커야 한다. 

그리고 나서 생각해 보니... (0과 1로 이루어져 있다는 것을 고심한게 힌트가 되었다. )

n k 일 떄의 값은 n k인데 0으로 끝나는 비트의 개수 + n k인데 1로 끝나는 비트의 개수이다. (핵심!)

-> 는 배열로 생각해 보았을 떄 [n][k]의 값은 = [n][k][0] + [n][k][1]가 된다. 

사실 위의 생각이 핵심이기는 한데... 진짜 어떻게 생각했냐고 하면 나도 잘 모르겠다. 2일넘게 고민한 것 같다.. 

그렇게 되면 [n][k][0]과 [n][k][1]의 값만 구하면된다! (0으로 끝나는 비트와 1로 끝나는 비트를 나누고 보니 서로 연산 방법이 다르기 때문에 나눴구나.. 하고 나눈 후에 뒤늦은 이해를 했다... 사실 이해하고 나눴어야 했는데 순서가 바뀌었다... 더 공부할 필요성을 절실히 느낀다..)

[n][k][0]은 0으로 끝나는 비트이므로 분명

. . . . . . . . .0 이 될 것이다.  이 다음에 0,1 모두 들어간다 하더라도 k(인접한 비트수)는 그대로 유지될 것이므로 

[n-1][k][0] + [n-1][k][1]이 될 것이다. 

왜냐하면 이 비트들은 . . . . . . . . . . 0 으로 끝났을 경우  . . . . . . . . . . 0에 0을 추가한 . . . . . . . . . . 00 이 되면 k는 유지되고 길이가 n이 되기 때문이다. 

[n][k][1]은 1로 끝나는 비트이므로 분명

. . . . . . . . . . 1이 될 것이다. 

이 경우 뒤에 1이 온다면 k(인접한 비트 수)가 하나 늘어날 것이므로 

[n-1][k][0] + [n-1][k-1][1]이 될 것이다.

. . . . . . . . . . 0로 끝났을 경우에는 1을 추가해도 . . . . . . . . . . 0 1로 k(인접한 비트 수)가 늘어나지 않지만 

. . . . . . . . . . 1로 끝났을 경우에는 1을 추가하면 . . . . . . . . . . 1 1로 k가 늘어나기 때문에 이전에 k-1개의 인접한 비트 수를 가진 비트열에 1을 추가하는 경우만 가능하다. 

그것을 그대로 구현하였다. 

코드에서 사실 21라인에서 i가 0부터 시작하기 때문에 바운더리처리를 해줘야하는게 맞으나.. 메모리구조상 에러가 나지 않아서 그대로 두었다.. 원래는 해주는 것이 맞다. 

PS. 

1. 지역변수로 큰 배열을 잡는것 보다 전역변수로 잡는 것을 추천 (6번 라인 같은 경우 3번 라인으로 빼는게...) 받았다. 

2. 정답률도 높았는데 머리가 안돌아가는지 정말 어려웠다..