[백준(baekjoon) 2193] 이친 수

문제

백준 2193

n(1…90)이 주어질 때, 길이가 n인 이친 수의 개수를 구하는 문제

• 이친 수 : 0으로 시작하지 않고, 11을 부문 문자열로 가지지 않는 이진 수
• 예시 : 1, 10, 101, 10101

해결

길이가 n인 이친 수는 길이가 n-1인 수의 끝자리를 기준으로 구할 수 있다.

1. n-1의 끝자리가 0일 때 : 뒤에 0과 1을 붙일 수 있다.
2. n-1의 끝자리가 1일 때 : 뒤에 0만 붙일 수 있다. (11은 불가하기 때문)

즉, 끝자리가 1, 0인 경우를 각각 저장해두고 이를 활용해 구하면 된다.

n	예시	이친 수의 총 개수	끝자리가 0인 개수	끝자리가 1인 개수
1	1	1	0	1
2	10	1	1	0
3	100 101	2	1	1
4	1000 1001 1010	3	2	1
5	10000 10001 10010 10100 10101	5	3	2

길이가 n인 이친 수는 다음과 같은 식을 세울 수 있다.

• 이친 수의 총 개수 = n-1의 끝자리가 0인 개수 * 2 + n-1의 끝자리가 1인 개수
  
  • why * 2? 위의 1번에 따라 2개로 늘어나기 때문
• 끝자리가 0인 개수 = n-1의 끝자리가 0인 개수 + n-1의 끝자리가 1인 개수
• 끝자리가 1인 개수 = n-1의 끝자리가 0인 개수

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.
8.        System.out.println(goTo(n)[0]);
9.    }
10.
11.    static long[] goTo(int n) {
12.        if (n == 1) return new long[]{1, 0, 1};
13.
14.        long[] current = new long[3];
15.        long[] before = goTo(n - 1);
16.        current[0] = before[1] * 2 + before[2];
17.        current[1] = before[1] + before[2];
18.        current[2] = before[1];
19.        return current;
20.    }
21.}

2. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        long[][] dp = new long[n][3];
8.        dp[0] = new long[]{1, 0, 1};
9.
10.        for (int i = 1; i < n; i++) {
11.            dp[i][0] = dp[i-1][1] * 2 + dp[i-1][2];
12.            dp[i][1] = dp[i-1][1] + dp[i-1][2];
13.            dp[i][2] = dp[i-1][1];
14.        }
15.
16.        System.out.println(dp[n-1][0]);
17.    }
18.}

결과

1. Top-Down 방식
2. Bottom-Up 방식