[백준][DP][2193] 이친수

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

- 소스코드

· 2차원 다이나믹

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	long[][] dp = new long[n+1][2];
	
	// 이친수는 0으로 시작하지 않는다.
	dp[1][1] = 1;
		
	for(int i=2; i<=n; i++){
		for(int j=0; j<2; j++){
			// 이친수에서는 1이 두번 연속으로 나타나지 않기 때문에
			if(j == 1){
				dp[i][j] = dp[i-1][0];
			}else{
				dp[i][j] = dp[i-1][0] + dp[i-1][1];
			}
		}
	}
		
	long ans = 0;
		
	for(int i=0; i<2; i++){
		ans += dp[n][i]; 
	}
		
	System.out.println(ans);
}

· 1차원 다이나믹

public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long[] d = new long[n+1];
        d[1] = 1;

        if (n >= 2) {
            d[2] = 1;
        }
	
	// 0으로 끝나는 경우 앞에 0과 1 모두 올 수 있다.
	// => d[i-1]
	// 1로 끝나는 경우 앞에 0만 올 수 있기 때문에 앞에 붙는
	// 0을 세트로 생각해서 i-2자리에 01을 붙인다고 생각
	// => d[i-2]
        for (int i=3; i<=n; i++) {
            d[i] = d[i-1] + d[i-2];
        }

        System.out.println(d[n]);
 }

- My Thinking

이친수 문제는 1차원 다이나믹과 2차원 다이나믹 두 가지 방식으로 문제를 풀 수 있다. 나의 경우에는 1차원 다이나믹으로 풀었지만, 2차원 다이나믹을 이용한다면 좀 더 쉽게 풀 수 있다. 이 문제도 처음에 풀 때 에러가 발생해서 이해를 할 수 없었는데 종만북에서 나온대로 입력값의 최소, 최대를 입력해보니, 최대값을 입력했을 때 쓰레기값이 나온다는 것을 알게되었다. 그래서 결과값을 출력하는 변수의 타입을 long으로 바꾸었더니 올바르게 출력되었다.