[KOITP] 인접한 비트의 개수

출    처 : http://koitp.org/problem/ICPC_2009GNY_ADJACENTBIT/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1241	648 (52%)	531

문제

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

• s_1 x s_2 + s_2 x s_3 + s_3 x s4 + ... + s(N-1) x s_N

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

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

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

1. 11100
2. 01110
3. 00111
4. 10111
5. 11101
6. 11011

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 1,000)

각 테스트 케이스의 첫 번째 줄에 세 정수 t, N, K가 공백으로 분리되어 주어진다. t는 테스트 케이스의 번호이다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스에 대해 테스트 케이스 번호와 인접한 비트의 개수가 k인 수열 S의 개수를 사이에 공백을 두고 한 줄에 하나씩 출력한다.

이 값은 2,147,483,647보다 작거나 같다.

힌트

예제 입력

10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90

예제 출력

1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518

< Comment >

 사실상 답을 보고 푼 것이나 마찬가지인 것 같습니다. 기본적으로 점화식은 세웠으나, 기저케이스에 대해 명확한 정의없이 진행하다보니 문제를 푸는데 오래 걸렸습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BitFriends {
	
	public static int T = 0;
	public static int N = 0;
	public static int K = 0;
	
	public static int dp[][][] = null;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		T = Integer.parseInt(br.readLine());
		int testCase = 0;
		for (int tc = 1 ; tc <= T ; tc++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			testCase = Integer.parseInt(st.nextToken());
			
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			dp = new int[2][N+1][N+1];
			
			for (int i = 1 ; i <= N ; i++) {
				dp[1][i][i-1] = 1;
			}
			dp[0][1][0] = 1;
			for (int i = 2 ; i <= N ; i++) {
				
				for (int j = 0 ; j < i; j++) {
					
					if (j == 0) {						
						dp[0][i][j] = dp[0][i-1][j] + dp[1][i-1][j];
						dp[1][i][j] = dp[0][i-1][j];
					} else {
						dp[0][i][j] = dp[0][i-1][j] + dp[1][i-1][j];
						dp[1][i][j] = dp[0][i-1][j] + dp[1][i-1][j-1];
					}
				}
			}
			
			
			bw.write("" + testCase + " " + (dp[0][N][K] + dp[1][N][K]) + "\n");
			bw.flush();
		}
		bw.close();
	}
}