[백준][DP][11726] 2 x n 타일링

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

소스코드 : 

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

- Category : 다이나믹 프로그래밍

- My Thiking

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

처음에는 다음과 같은 방식으로 접근을 하려해서 오류가 났다. + 1을 하는 것은 타일 2 x 1 이나 1 x 2 중 하나를 선택하는 것인데 이 문제 같은 경우는 끝에 2 x 1 블럭 또는 1 x 2 가 올 경우로 각각 나누어서 dp[i-1]과 dp[i-2]의 합으로 푸는 것이 보다 정확하다. 2번째 문제로는 항상 dp[0]을 무엇으로 두느냐에 대한 문제였다. 그래서 최백준님께 강의를 들으면서 질문을 드렸고 대답은 다음과 같았다.

`d[0] = 1`을 주는 경우는 경우의 수 문제의 경우에 주로 사용합니다.  1, 2, 3더하기 같은 경우에는  `d[0] = 1`의 의미가 보통 0을 만드는 방법이 1가지라는 뜻입니다.  d[3]을 채우는 경우에 경우는 수를   * 0개를 사용해서 만든 2을 만드는 방법 + 그 뒤에 1을 사용한 방법 = d[3-1]  * 0개를 사용해서 만든 1을 만드는 방법 + 그 뒤에 2을 사용한 방법 = d[3-2]  * 0개를 사용해서 만든 0을 만드는 방법 + 그 뒤에 3을 사용한 방법 = d[3-3]  `d[0] = 0`으로 하고 문제를 해결하려면, 수를 1개를 사용한 방법, 즉 d[1] = d[2] = d[3] = 1을 미리 초기화를 한 다음에 사용해야 합니다.

나의 경우에는 d[0]을 초기화 하지 않았기 때문에 dp[1], dp[2]를 초기화해서 사용해서 접근할 수 있었다.