[백준] DP - 2193번, 이친수

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

11057번 안 푼 줄 알았는데, 무려 한 달 전에 풀었던 거였다...

그래서 2193번 이어 풀었음. 풀면서 느낀 건 10844번 익혔던 개념을 제대로 이해 못했다는 것.

다시 이해하고 문제 풀이에 집중함.

 

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

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

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

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

 

출) 첫째 줄에 N자리 이친수의 개수를 출력한다.

---

풀이1 - 2차원 배열

1. 테이블 정의

: 0과 1로 이루어진 이진수 중 다음의 조건을 만족하는 N자리 이친수의 개수를 구하기.

• 이친수는 0으로 시작하지 않는다.
• 1을 두번 연속 가지지 않는다.

2. 점화식 : 2차원 배열 활용

• j = 0 일때, dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
• j = 1 일때, dp[i][j] = dp[i-1][j-1]

점화식 모습이 10844번과 유사한 이유는 그와 비슷한 형식으로 생각했기 때문.

i는 자릿수, j는 자릿값. 이진수이기 때문에 자릿값은 0과 1밖에 못 온다.

현재 값은 직전 자릿수 값에 영향 받는다.

현재 자릿값이 0이냐 1이냐에 따라 올 수 있는 값이 다름.

표를 보시면 이해가 갈 겁니다.

 

3. 초기값 : dp[1][i] = i;

 

코드

import java.util.*;

public class num_2193 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long dp[][] = new long[n+1][2];

        for(int i=0; i<2; i++) {
            dp[1][i] = i;
        }
        for(int i=2; i<n+1; i++) {
            for(int j=0; j<2; j++) {
                if (j == 1) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1];
            }
        }
        long result = 0;
        for(int i=0; i<2; i++) {
            result += dp[n][i];
        }
        System.out.println(result);
        sc.close();
    }
}

 

 

 

풀이2(점화식 도출 부분만 서술.) - 1차원 배열

1. 이진수, n자리 올 수 있는 수는 0과 1.

• 0일 경우, 앞에는 0 혹은 1 모두 가능. 0 or 1(n-1), 0(n) ▶ D[n-1]
• 1일 경우, 앞에는 0만 가능. 0 or 1(n-2), 0(n-1), 1(n)
  • n-1번째가 0이므로 n-2에는 0 또는 1 가능. ▶ D[n-2]

2. 점화식: D[n] = D[n-1] + D[n-2]

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String args[]) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int count = Integer.parseInt(br.readLine());
            long d[] = new long[count+1];
            // d[n] = n자리 이친수.
            d[0] = 0;
            d[1] = 1;
            for (int i = 2; i <= count; i++){
                d[i] = d[i-1] + d[i-2];
            }
            System.out.println(d[count]);
    }
}

---

스스로 2차원 배열을 활용해 풀고보니(풀이1) 훨씬 간단한 점화식을 사용한 풀이가 있었다.

더 찾아보니 1차원 배열을 활용한 방식(풀이2)이었다.

후자가 bufferedReader를 사용해서인지 메모리와 시간도 훨씬 절약됐다.

 

나도 br썼으면 훨씬 빠르게 했을까?

일단 이해하고 푸는데 집중하느라 더 편한 방식을 선택했는데,

메모리 효율을 위해 br 사용을 더 많이 해야겠다.

 

지난번엔 Top-Down(재귀) 방식을 봤는데 이번엔 2차원 배열 아닌,

1차원 배열로 푸는 방식도 보게 되었다. 시간되면 다른 방식들도 도전해봐야겠다.