[Algorithm/C] BOJ.2698 인접한 비트의 개수

the_number_of_adjacent_bits.c

Click to download.

접근 방법

1. 처음 든 생각 : Combination 도저히 풀리지 않음.

2. 배열을 만들어 볼까 생각 이것도 안풀림.

3. Dynamic programming으로 접근해야함.

#include <stdio.h>

int theNumberOfCase[102][102][2]={0};

int main(int argc, char * argv[])

{

int testCase;

int lenSequence;

int adjacentBits;

int i,j;

theNumberOfCase[1][0][0]=theNumberOfCase[1][0][1]=1; // 0 이나 1을 뜻함

for(lenSequence=2; lenSequence<102; lenSequence++)

{

for(adjacentBits=0; adjacentBits<102

&& lenSequence>adjacentBits

; adjacentBits++)

{ /*sequence의 길이와 인접한비트의수가 주어졌으며 0으로 끝나는 경우의 수는

**0으로 끝난다면 그 앞이 0이 올때나 1이 올때나 경우의 수는 변함이 없다. 따라서,

**sequence-1의 길이와 인접한비트의수는 같고 0으로 끝나는 경우의 수 + 1로 끝나는 경우의 수이다.*/

theNumberOfCase[lenSequence][adjacentBits][0] 

=theNumberOfCase[lenSequence-1][adjacentBits][0] + theNumberOfCase[lenSequence-1][adjacentBits][1];

/*sequence의 길이와 인접한비트의수가 주어졌으며 1으로 끝나는 경우의 수는

**1으로 끝난다면 그 앞이 1이 올때만 경우의 수가 변한다. 따라서,

**sequence-1의 길이와 인접한 비트의수는 같고 0으로 끝나는 경우의 수 + 인접한 비트의수-1 이며 1로 끝나는 경우의 수이다.*/

theNumberOfCase[lenSequence][adjacentBits][1]

=theNumberOfCase[lenSequence-1][adjacentBits][0] + theNumberOfCase[lenSequence-1][adjacentBits-1][1];

}

}

scanf("%d",&testCase);

while(testCase--)

{

scanf("%d %d",&i,&j);

printf("%d",theNumberOfCase[i][j][0]+theNumberOfCase[i][j][1]);

}

return 0;

}

문제 출처 - https://www.acmicpc.net/problem/2698