백준 2193: 이친수 [JAVA]

[문제 링크]

https://www.acmicpc.net/problem/2193

[난이도]

- Silver 3

 

[알고리즘]

- DP

 

[코드]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        // 초기값 설정
        dp[1][0] = 0;
        dp[1][1] = 1;

        // DP 배열 채우기
        for (int i = 2; i <= N; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }

        // 최종 결과 출력
        long result = dp[N][0] + dp[N][1];
        System.out.println(result);
    }
}

[풀이]

1. 문제 이해

0 으로 시작하지 않는다.

1이 두번 연속으로 나타나지 않는다.

 

2. dp 배열 정의

 n=1 일때  {1} = 1
 n=2 일때 {10} = 1
 n=3 일때 {100, 101} = 2
 n=4 일때 {1000, 1001, 1010} = 3
 n=5 일때 {10000, 10001, 10010, 10100, 10101} = 5
 n=6 일때 {100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010} = 8

dp[n] = dp[n-1]의 길이만큼 for문을 돌며 dp[n-1]의 각 원소뒤에 0과 1을 추가한다. 마지막 자리가 1일경우 0만 추가.
새로만든 원소들을 dp[n]에 넣는다.

이 로직을 점화식으로 만들고 구현할 아이디어가 모자라서 챗gpt의 도움을 빌렸다.

 

dp[i][0] : i자리 이친수 중 마지막 자리가 0인 이친수의 개수

dp[i][1] : i자리 이친수 중 마지막 자리가 1인 이친수의 개수

 

3. 초기값 설정

dp[1][0] = 0

dp[1][1] = 1

 

4. 점화식 작성

dp[i][0] = dp[i-1][0] + dp[i-1][1] : 마지막 자리가 0인 경우는 i-1자리 이친수에서 마지막 자리가 0인 경우와 1인 경우 모두에서 올 수 있다.

dp[i][1] = dp[i-1][0] : 마지막 자리가 1인 경우는 i-1자리 이친수에서 마지막 자리가 0인 경우에서만 올 수 있다.

 

5. 출력

N자리의 이친수의 개수 = dp[N][0] + dp[N][1]