[백준,BOJ 2193] 이친수( JAVA 구현)

-내 생각

  우선 이런 류의 문제는 쉬운 계단 수는 오르막 수와 같은 방식으로 풀어야 한다는 느낌은 알 것 같다. 그래서 이번 문제의 경우는 dp배열의 설계는 제대로 되었고, 거기서 규칙을 찾는 것 또한 잘 찾았다. 그러나 오답 처리를 받아 어디가 문제일까 고민해보다가 n의 최댓값인 90을 넣어보니 역시 int형 데이터의 범위를 벗어나 제대로 된 답이 나오지 않았다. 항상 테스트 케이스의 범위 중 최댓값을 넣어보는 습관을 들여야 할 것 같다.

 

-해법

  해법은 간단하다. 쉬운 계단 수나 오르막 수 처럼 0과 1을 끝자리 기준으로 두고 표를 그려보면 된다. 우선 N이 1일 경우 초기화를 시켜주어야 하는데, 끝 자리가 0일 경우는 올 수 없다. 왜냐하면 0으로 시작하는 경우는 존재하지 않는다고 문제에서 언급했기 때문이다. 그렇다면 끝 자리가 1이 오는 경우는 1 한 개뿐이다. 다음 N이 2일 경우에 0이 끝자리로 오는 경우를 구해야 하는데, 문제에서 언급한 또 다른 내용은 1이 연속해서 나올 수 없다는 점이다. 그러므로 0이 끝자리로 올 때는 0의 앞자리로 오는 수가 끝자리가 0이든 1이든 상관이 없지만, 끝 자리가 1로 끝날 때는 1의 앞자리로 오는 경우가 1로 끝나는 경우는 안된다는 소리다. 즉, 0이 끝자리일 경우는 이전 자리 수의 0으로 끝나는 경우의 수 + 1로 끝나는 경우의 수가 되고, 1이 끝자리일 경우는 이전 자리 수가 0으로 끝나는 경우만 가능하다.

	0	1
N = 1	0	1
N = 2	1	0
N = 3	1	1
N = 4	2	1

  이를 점화식으로 표현해보면,

if(j==0) {  // 0으로 끝나는 경우는 앞의 경우의 수가 0 또는 1로 끝나도 무방하므로 두 가지를 더해주고
   dp [i][j] = dp [i-1][0] + dp [i-1][1];
} else {  // 1로 끝나는 경우는 앞의 경우의 수가 1로 끝나는 경우는 배제해야 하므로 0으로 끝나는 경우만 취한다.
   dp [i][j] = dp [i-1][0];
}

 

import java.util.*;
import java.math.*;
public class Main {
	
	static long dp[][] ; // 데이터 타입에 유의한다.
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n= sc.nextInt();
		
		dp = new long [n+1][2];
		
        //N이 1일 경우는 초기화해둔다.
		dp[1][0] = 0; 
		dp[1][1] = 1;
		
		for(int i=2;i<=n;i++) {
			for(int j=0;j<2;j++) {
				if(j==0) {
					dp[i][j] = dp[i-1][0] + dp[i-1][1];			
				}else {
					dp[i][j] = dp[i-1][0];
				}
			}
		}
		
		long sum =0;
		for(int i=0;i<2;i++) {
			sum+=dp[n][i];
			
		}
		
		System.out.println(sum);
		
		
		
		
		
	}
	
}