[JAVA] 백준 2193 DP

 

 

 

2193번: 이친수

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

풀이

이친수의 첫 자리수는 1이 반드시 와야하기 때문에 첫 자리와 두번째 자리수는 10으로 고정된다.

따라서 현재 자릿수의 i - 2부터 시작해서 자리수가 3이 될때까지 반복하면서 이전에 계산해두었던 이친수 갯수를 더해주면 된다.

예를 들어 5자리의 이친수 개수를 구하라는 문제가 있을 때

• now = 3
  • A[5] += A[3]; 이후 반복 종료
  • A[5] += 3; (2자리가 남은 경우 해당 자리의 경우의 수는 3개, ex) 10010, 10001, 10000)

5자리의 이친수 개수는 6이 나온다.

📌 기본 배열 초기화

        long[] A = new long[N];
        A[1] = 1;
        for(int i=2; i<5 && i < N; i++ ) {
            A[i] = i - 1;
        }

• 5이전의 값들은 미리 초기화 해주었다.
• 반복문으로 값을 넣은 이유는 해당 초기화되는 값들보다 요구하는 자리수가 더 작을 경우를 방지하였다. (ArrayOutOfBoundException)

📌 DP를 통해 값을 해결

        for(int i=5; i<N; i++){
            int now = i - 2;
            while (now > 2){
                A[i] += A[now--];
            }
            A[i] += 3;
        }

• 현재 값의 자릿수를 줄여나가면서 A[now]의 기존에 구해놓은 값을 사용하여 문제를 해결하였다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+1;

        long[] A = new long[N];
        A[1] = 1;
        for(int i=2; i<5 && i < N; i++ ) {
            A[i] = i - 1;
        }
        for(int i=5; i<N; i++){
            int now = i - 2;
            while (now > 2){
                A[i] += A[now--];
            }
            A[i] += 3;
        }
        System.out.println(A[N-1]);
    }
}

결과