[BOJ][Java] 2193번 이친수

문제 설명

문제 링크 : https://www.acmicpc.net/problem/2193

 

이 문제는 동적 계획법(DP)을 사용하면 해결할 수 있는 기본적인 문제이다.

DP의 핵심은 문제를 작은 부분으로 나누고 그 부분들을 이용하여

큰 문제를 해결하는 것이다.

이 과정에서 점화식을 이용하게 되는데, 이때 점화식은 유일하게 존재하는 게 아닌 푸는 사람마다 다른 점화식을 도출할 수 있다.

 

먼저 문제의 조건을 살펴보면

이친수의 시작조건은 무조건 1이어야 한다. 또한 1이 연속으로 나올 수 없다.

이런 조건을 가지고 그림을 그려가며 조건을 시각화해보면 아래와 같다.

 

위와 같이 1은 0으로만, 0은 0과 1로 변형할 수 있다는걸 알 수 있다.

이때 1과 0을 각각의 DP배열로 만들거나 2차원 배열을 통해 해결할 수도 있지만

하나의 1차원 배열로도 해결할 수 있다.

 

단 조건이 붙기 때문에 입력값의 시작인 1과 2의 경우 따로 처리를 해줘야 한다.

 

package boj;

import java.util.*;

public class BOJ2193 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

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

        if(N == 1 || N == 2){
            System.out.println(1);
            return;
        }

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

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