[BOJ] 백준 2698번 인접한 비트의 개수 (Java)

#2698 인접한 비트의 개수

난이도 :  골드 4

유형 : DP

2698번: 인접한 비트의 개수

▸ 문제

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과 k는 100을 넘지 않는 자연수이다.

▸ 출력

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

 

문제 풀이 

문제에 대한 접근방식이 잘못되어 꽤나 오래 헤맸다. 메모이제이션 기능을 간과하고 data를 String으로 다루다가 시간초과가 발생했다. 그래서 다시 각잡고 제대로 bottom-up 상향식으로 풀이했다.

📚 조건

   ∙ 테스트 케이스의 수 T (1 <= T <= 1,000)

   ∙ 수열 S의 크기 n, 인접 비트의 개수 k (1<= n,k <= 100)

 

 

dp[수열 크기][인접 비트의 갯수][n자리의 비트]라고 설정하자.

 

초기값은 다음과 같다.

dp[1][0][1] =1; // 1로 시작하는 수열S

dp[1][0][0] =1; // 0으로 시작하는 수열S

 

1) n번째 비트가 1일 때

  1-1) 인접한 비트의 갯수 그대로  ( 0 1 )

         dp[n][k][1] += dp[n-1][k][0];

 

  1-2) 인접한 비트의 갯수 +1  ( 1 1 )

         dp[n][k][1] += dp[n-1][k-1][1];

 

2) n번째 비트가 0일 때

  2-1) 인접한 비트의 갯수 그대로 ( 0 0 , 0 1 )

       dp[n][k][0] += dp[n-1][k][0] + dp[n-1][k][1];

dp[1][0][1] =1; // 1
dp[1][0][0] =1; // 0
for(int k=0; k<101; k++) {
	for(int n=2; n<101; n++) {
		dp[n][k][1] += dp[n-1][k][0];
		if(k!=0) {
			dp[n][k][1] += dp[n-1][k-1][1];
		}
		dp[n][k][0] += dp[n-1][k][0] + dp[n-1][k][1];
	}
}

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[][][] dp;
	static long res =0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		
		dp = new int[101][101][2];
		
		dp[1][0][1] =1; // 1
		dp[1][0][0] =1; // 0
		for(int k=0; k<101; k++) {
			for(int n=2; n<101; n++) {
                dp[n][k][1] += dp[n-1][k][0];
				if(k!=0) {
					dp[n][k][1] += dp[n-1][k-1][1];
				}
				dp[n][k][0] += dp[n-1][k][0] + dp[n-1][k][1];
			}
		}
			
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());			
			
			System.out.println(dp[n][k][0] + dp[n][k][1]);
		}
	}
}

 

Top-down 풀이 코드 

이를 재귀호출 코드로 풀이하면 다음과 같다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int n,k;
	static int[][][] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		dp = new int[100][100][2];
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				Arrays.fill(dp[i][j], -1);
			}
		}
			
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());			
			
			int a = solve(n-1,k,0);
			int b = solve (n-1,k,1);
			System.out.println(a+b);
		}
		
	}
	
	static int solve(int len, int adNum, int bit) {
		
		if(len ==0) { 
			if (adNum ==0) return 1;
			return 0;
		}
		
		if(dp[len][adNum][bit] != -1) return dp[len][adNum][bit]; 
		
		int res =0;
		if(adNum==0) {
			if(bit ==1) {
				res += solve(len-1, adNum, 0);
			}else {
				res += solve(len-1, adNum, 1);
				res += solve(len-1, adNum, 0);
			}
		}else {
			if(bit ==1) {
				res += solve(len-1, adNum-1, 1);
				res += solve(len-1, adNum, 0);
			}else {
				res += solve(len-1, adNum, 1);
				res += solve(len-1, adNum, 0);
			}
			dp[len][adNum][bit] = res;
		}
		return res;
	}
}