백준 11726번
https://www.acmicpc.net/problem/11726

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력

2

9

예제 출력

2

55

생각하기

동적계획법에서 이전 문제인 1, 2, 3더하기와 거의 90프로 이상의 싱크로율 문제이다.

동적계획법에 대해서 개념을 잡기는 아주 좋은 문제라고 생각한다.

그 전에 풀때는 동적계획법에 대해서 조금 알듯 말듯 했는데, 이제 memoization과 동적계획법에 대해 조금은 알 것 같다.

여기서 문제를 잘 이해해보면 사실 단순하게 1과 2를 사용한 조합일 뿐이다.

n이 1일때는 1이고
2는 2
3은 3
4는 5

여기서 보이는 규칙은 n = (n - 1 + n - 2) 라는 규칙이 생긴다.
우리는 이 반복되는 규칙을 가지고 정답을 찾을 수 있다.

그리고 이 문제에서 주의해야 할 점은 마지막에
직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

10007의 나머지값을 까먹으면 안된다.

동작

		int n = Integer.parseInt(br.readLine());
		memoization = new int[1001];

		memoization[1] = 1;
		memoization[2] = 2;
		memoization[3] = 3;
		memoization[4] = 5;

먼저 테스트케이스 n값을 만들어 주고

우리는 위에서 말했듯이 1과 2의 조합이므로 1과 2의 값은 memoization배열에 값을 넣어주면된다.

여기서 나는 그냥 3과 4를 넣어준 것이기 때문에 굳이 다른 분들은 넣어주지 않으셔도 상관없다.

이제 값을 찾기 위한 dp()메소드를 실행시켜보자

	static void dp(int num) {

		for(int i=4; i<=num; i++) {
			if(memoization[i] == 0) {

				memoization[i] = (memoization[i - 1] + memoization[i - 2]) % 10007;				
			}
		}

	} // End of result

dp 함수는 정해진 규칙을 반복대로 수행해서 값을 memoization배열에 저장한다.

우리가 찾는 값이 num은 이전 배열과 그 이전의 배열값의 합이 된다.

즉, memoization[i] = (memoization[i - 1] + memoization[i - 2]) % 10007;
이렇게 되는 것이다.

여기서 중요한 점

나는 마지막에 결과를 출력할 때 System.out에서 % 10007을 붙여줘서 나머지값을 넣어줬지만
알고보니 memoization배열에 저장할 때 부터 10007을 나눈 값을 넣어주어야했었다.

코드

import java.io.*;

public class Main {
	static int memoization[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		memoization = new int[1001];

		memoization[1] = 1;
		memoization[2] = 2;
		memoization[3] = 3;
		memoization[4] = 5;

		dp(n);

		System.out.println(memoization[n]);
	} // End of main

	static void dp(int num) {

		for(int i=4; i<=num; i++) {
			if(memoization[i] == 0) {

				memoization[i] = (memoization[i - 1] + memoization[i - 2]) % 10007;				
			}
		}

	} // End of result
} // End of class