[백준 2193 / JAVA] 이친수

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

2193번: 이친수

 

꽤 신기했던 DP 문제였다.

 

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

public class Main {
    static int N;

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

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


        for (int i = 2; i <= N; i++) {
        	dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
            // 1 연속 두번 못 옴
        	dp[1][i] = dp[0][i - 1];
        }

        System.out.println((dp[0][N] + dp[1][N]));
    }

}

처음에 작성했던 코드이다. 평범한 dp 방식으로 풀었다.

dp[0] 부분은 0이 올 때, dp[1]은 1이 올 때이다.

N이 1일 때는 0은 오지 못하므로 dp[1][1]에만 1을 넣어준다.

1은 두 번 연속으로 오지 못하므로 1인 올 경우는 0을 넣었던 이전 경우를 넣어준다.

0은 이전에 0, 1 둘 다 올 수 있으므로 이전 경우 두가지를 모두 더해준다.

그런데 위 코드를 작성하고 출력하는데 출력부분에서 규칙이 보였다...

 

N이 각각 1, 2, 3... 일 때 출력이 1 1 2 3 5 8 ... 이었다...

피보나치 수열이다. 

 

그래서 코드를 수정했다.

 

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

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // long[][] dp;
        long[] fibo;
        N = Integer.parseInt(br.readLine());

        // dp = new long[2][N + 1];
        fibo = new long[90];
        // dp[1][1] = 1;
        fibo[0] = 1;
        fibo[1] = 1;

        // for (int i = 2; i <= N; i++) {
        // dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
        // dp[1][i] = dp[0][i - 1];
        // }
        for (int i = 2; i < N; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }

        System.out.println(fibo[N - 1]);
        // System.out.println((dp[0][N] + dp[1][N]));
    }

}

 

피보나치 수열로도 풀린다.