[백준 11727]https://www.acmicpc.net/problem/11727
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
이전의 결과가 뒤의 결과를 도출하는데 도움되는 문제니까 Dynamic Programming(DP : 동적계획법)으로 풀어야 할 것 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[1001];
dp[1] = 1;
dp[2] = 3;
for (int i = 3; i <= n; i++) { // 점화식
dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
}
System.out.println(dp[n]);
}
}
이 문제는 이렇게 i번째 경우의 수가 (i - 1)번째와 (i - 2)번째 경우의 수에 의해 결정된다.
점화식은 dp[i] = dp[i - 1] + 2 * dp[i - 2]로 세울 수 있다.
dp문제는 점화식을 세우는 게 가장 중요한데, 여러 문제를 풀어보면서 문제에서 주어진 패턴을 파악하고 점화식으로 나타내는 연습을 많이 해야겠다.