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

문제 링크

https://www.acmicpc.net/problem/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보다 작거나 같다.

구조화

백트래킹으로 접근 -> dp로 변환

1은 무조건 1이 만날때만 1이 되고, 0은 다 0으로 바뀐다는 것을 고려하여

pre*pre로 값을 더해줌

오답 노트

백트래킹에서 dp로 넘어가려고 할때 변수의 인자만큼 dp 배열 만들기! -> 친구의 조언

소스 코드

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

public class Main {

    static int n, k, ans;
    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());
        dp = new int[100][100][2];

        while (t-- > 0) {
            ans = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    Arrays.fill(dp[i][j], -1);
                }
            }

            System.out.println(loop(0, 0, 0));
        }
    }

    static int loop(int cnt, int val, int pre) {
        if (cnt >= n) {
            if (val == k) {
                return 1;
            }
            return 0;
        }

        if (dp[cnt][val][pre] != -1) return dp[cnt][val][pre];

        dp[cnt][val][pre] = 0;

        dp[cnt][val][pre] += loop(cnt+1, val+(pre*pre), pre);

        if (pre == 1)
            dp[cnt][val][pre] += loop(cnt+1, val, 0);
        else
            dp[cnt][val][pre] += loop(cnt+1, val, 1);

        return dp[cnt][val][pre];
    }
}