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

문제 링크

2698번: 인접한 비트의 개수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 0과 1로 이루어진 수열 S가 존재합니다.

2. S의 인접한 비트의 개수는 문제에서 주어진 연산식을 따르게 됩니다.

3. 수열이 길이가 n이고 인접한 비트의 개수가 k인 수열의 모든 경우의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 수열에 대한 인접한 비트의 값에 대한 경우의 수를 점화식을 통해 탐색합니다.

 

3. 탐색으로 값 중 길이가 n이고 k인 경우의 수를 결과로 출력합니다.

 

인접한 비트의 개수 구하기(DP)

 

0과 1으로 이루어진 수열 = 2진수

 

▶︎ 이진수의 길이는 길이가 증가할 때마다 아래와 같이 진행됩니다.

 

수열의 길이가 증가될 때마다 이전 2진수에서 맨 앞에 0, 1이 추가되는 것을 확인하실 수 있습니다.

 

각 수열의 길이가 증가될 때마다 0, 1이 붙었을 때 비트의 값을 살펴보면 아래와 같습니다.

 

현재 수열의 길이 n일 때

 

0이 붙었을 때 : 길이가 n-1인 수열에 비트의 값 경우의 수와 동일합니다.

 

1이 붙었을 때 : 10__, 11__ 의 2가지 형태로 나뉘어집니다.

 

10__일 때 : 길이가 n-2인 수열에 비트의 값 경우의 수와 동일합니다.

 

11__일 때 : 비트의 값이 항상 1이 기본적으로 존재하기 때문에 길이가 n-2인 수열에 (비트의 값 - 1) 경우의 수와 동일합니다.

 

해당 내용을 그림으로 살펴보면 아래와 같습니다.

 

 

위 과정을 다이나믹 프로그래밍 테이블로 살펴보면 아래와 같습니다.

 

수열의 길이\비트의 값	0	1	2	3
0	1	0	0	0
1	2	0	0	0
2	3	1	0	0
3	5	2	1	0
4	8	5	2	1

위 테이블을 기반으로 점화식을 살펴보면

 

DP[i][j] = DP[i-1][j] + DP[i-2][j] + (DP[i-1][j-1] - DP[i-2][j-1])

 

DP[i-1][j] : 맨 앞에 0이 붙을 때

 

DP[i-2][j] : 맨 앞에 1이 붙으며 그 뒤에 0으로 10__일 때

 

DP[i-1][j-1] - DP[i-2][j-1] : 맨 앞에 1이 붙으며 그 뒤에 1으로 11__일 때

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

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

 

 

 

2. 수열에 대한 인접한 비트의 값에 대한 경우의 수를 점화식을 통해 탐색합니다.

 

1번 위치일 때 나무의 거리

 과정을 다이나믹 프로그래밍 테이블로 살펴보면 아래와 같습니다.

 

수열의 길이\비트의 값	0	1	2	3	4
0	1	0	0	0	0
1	2	0	0	0	0
2	3	1	0	0	0
3	5	2	1	0	0
4	8	5	2	1	0
5	13	10	6	2	1
...

 

 

 

3. 탐색으로 값 중 길이가 n이고 k인 경우의 수를 결과로 출력합니다.

 

 

10개의 길이가 n일 때 k인 경우의 수에 결과

6
63426
1861225
168212501
44874764
160916
22937308
99167
15476
23076518

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 수열의 정보를 띄어쓰기 기준 나누었습니다.
• 점화식을 통해서 수열 길이 기준 비트 점수에 대한 배열을 탐색합니다.
• 탐색을 통해 T개의 비트 점수 경우의 수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int[][] DP = new int[101][101];
        //기본 수열의 정보 세팅(x, 0, 1)
        DP[0][0] = 1;
        DP[1][0] = 2;
        //점화식을 통해 길이가 i일 때 인접한 비트의 개수가 j인 값 탐색하기
        for(int i=2;i<=100;i++){
            for(int j=i-1;j>0;j--){
                DP[i][j] = DP[i-1][j] + DP[i-2][j] + (DP[i-1][j-1] - DP[i-2][j-1]);
            }
            //인접한 비트의 개수가 0일 때
            DP[i][0] = DP[i-1][0] + DP[i-2][0];
        }
        StringTokenizer st;
        //각 주어진 길이가 n이고 인접한 비트의 개수가 k일 때 경우의 수 BufferedWriter 저장
        for(int tc=1;tc<=T;tc++){
            st = new StringTokenizer(br.readLine()," ");
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            bw.write(String.valueOf(DP[n][k]));
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}