[백준] 2193 이친수 자바(Java)

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

2193번: 이친수

 

점화식

 

풀이 1.

현재 위치에서 값이 0이면 이전 값은 1과 0이 올 수 있다.

dp[digit][0] = dp[digit - 1][1] + dp[digit - 1][0];

현재 위치에서 값이 1이면 이전 값은 0만 올 수 있다.

dp[digit][1] = dp[digit - 1][0];

 

풀이 2.

d[i] = d[i-2]+d[i-1]

이런 식으로 푸는 방식이 있는데, 직접 나열하면서 규칙을 찾다 보면 보이는 식이다.

 

위 사진과 같은 규칙이 나오는 걸 볼 수 있다.

맨 앞자리값과 그다음값은 1과 0으로 고정되었다.

n = 5라고 가정하고,, n = 4인 경우 1을 제외한 값은 0부터 시작하는 값이고, n = 3인 경우 1부터 시작하는 값이 된다.

 

소스 코드

// 풀이 1

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

public class Main {

    static long[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

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

        for (int digit = 2; digit <= n; digit++) {
//          현재 위치에서 값이 0이면 이전 값은 1과 0이 올 수 있다.
            dp[digit][0] = dp[digit - 1][1] + dp[digit - 1][0];
//          현재 위치에서 값이 1이면 이전 값은 0만 올 수 있다.
            dp[digit][1] = dp[digit - 1][0];
        }

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

 

// 풀이 2

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

public class Main {

    static long[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        
        dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int digit = 2; digit <= n; digit++) {
            dp[digit] = dp[digit - 2] + dp[digit - 1];
        }
        System.out.println(dp[n]);
    }
}