[DP 연습] BOJ_11726 2×n 타일링 (S3)

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

11726번: 2×n 타일링

이걸 생각해 내기까지도 1시간이 걸렸다. dp[0]부터 dp[4]까지 다 써보고 나서 차츰차츰 줄여가면서 점화식을 세워보려고 노력했다. 풀면서도 긴가민가 하고 아몰라! 하고 이클립스에서 돌려봤더니 출력도 잘 나오고 돌아가서 백준에 올려봤더니 틀렸다고 떴다!

구글링해서 코드를 비교해보니까 % 10007 부분을 반복문에서 처리해주는 차이가 있길래 반복문으로 올려줬더니 런타임 에러 (ArrayIndexOutOfBounds) 오류가 다시 났다. 그래서 코집사 코드를 보니까 배열 길이를 +2 해줬길래 나도 그렇게 고쳐줬더니 맞았다고 떴다. 맞은건 기쁜데 왜 % 10007 자리를 옮겨주어야 하는지도 모르겠고, 왜 +2를 해줘야 하는지도 모르겠어서 화가 났다. 내일 보충시간에 보충 교수님께 물어봐야 할 것 같다. 아 그리고 이것저것 이클립스에서 다 돌려보고 백준에서 돌려보게 직접 넣어볼 수 있는 예제도 백준에 많이많이 있었으면 좋겠다.

package algo0921;

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

// 2*n 타일링
public class BOJ_11726 {
	public static void main(String[] args) throws NumberFormatException, IOException {

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

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

		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;

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

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

package algo0921;

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

// 2*n 타일링
public class BOJ_11726_sol {
	public static void main(String[] args) throws NumberFormatException, IOException {

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

		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N + 2];

		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;

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

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