백준 2193 이친수 Java

dp문제인 이친수이다.

나 뿐만 아닌 누구든 문제 제목을 보고 이천수 선수를 떠올렸다는 것에 약 천원을 걸겠다.

이 문제 역시 혼자 정답인 점화식을 생각해내는 것엔 실패 했다. 갈 길이 멀다.

 

마지막 자리에 올 수 있는 경우의 수가 0과 1이기 때문에

dp[n-1]+2를 하고 마지막이 1인 경우엔 1이 못오기에

-1을 해서 dp[n-1]+2-1을 하면 되지 않을까? 생각했다.

확신은 없었고 당연히 틀린 답이였다..

 

마지막 자리인 n자리에 0과 1이 올 수 있다는 것은 알겠고..

마지막에서 한칸 앞인 n-1의 자리에 1이 온다면 0밖에 올 수 없다는 것은 알았다.

하지만 n-1의 자리에 1이 오는 경우의 수를 생각해내지 못했다.

 

온라인 강의였지만 최백준님은 이런 나를 비웃기라도 하듯 명쾌한 해법을 보여주셨다..

n번째 자리에 0이 올 땐 n-1의 숫자가 0 또는 1 상관이 없으므로 dp[n-1]만큼 정답에 더하고

n번째 자리에 1이 올 땐 n-1의 자리에 무조건 0이 와야하기 때문에  dp[n-1]에서 0이 올때를 생각해서

dp[n-2]을 정답에 더하면 된다고.. 

따라서 점화식은 dp[n] = dp[n-1]+dp[n-2]이다.

 

도대체 이런 생각을 어떻게 하는지 모르겠다.

혼자서 이런 점화식을 떠올릴 수 있는 사람들을 존경한다.

 

그렇게 해설을 듣고 정답을 제출했는데

호환마마보다 무섭다는 '틀렸습니다'가 떴다.

 

알고보니 dp배열을 int로 선언해줘서 n이 크면 값이 int형으로 담을 수 있는 수보다 컸기 때문이였다.

암튼 제출하기전에 혼자 n에 들어갈 수 있는 수들 중 가장 작은 수와 가장 큰수는 기본적으로

검사해보고 제출하는 버릇을 들여야 겠다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long [] dp = new long[n+1];
        
        dp[0] = 0;
        dp[1] = 1;
 
        for(int i=2; i<=n; i++)
            dp[i] = dp[i-1]+dp[i-2];
        
        System.out.println(dp[n]);
    }