boj)11727 - 2xn 타일링 2
2020. 9. 16. 18:24ㆍPS/boj
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// # 2xn 타일링 2
public class boj_11727 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] dp = new int[1001];
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
dp[1] = 1; dp[2] = 3;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i-1] + dp[i-2]*2) % 10007;
}
System.out.println(dp[n]);
}
}
- 2xn의 타일을 채울때 마지막에 올 수 있는 타일은 세로2 타일 1개, 가로1 타일 2개, 가로세로2 타일 1개
- 이렇게 3가지 방법으로 올 수 있다.
- 세로2타일의 경우는 dp[n-1], 나머지 두 방법은 모두 dp[n-2]라서 점화식을 세워보면
- dp[n] = dp[n-1] + 2 * dp[n-2]와 같다.
'PS > boj' 카테고리의 다른 글
boj)11052 - 카드 구매하기 (0) | 2020.09.17 |
---|---|
boj)9095 - 1, 2, 3 더하기 (0) | 2020.09.16 |
boj)11726 - 2xn 타일링 (0) | 2020.09.16 |
boj)1463 - 1로 만들기 (0) | 2020.09.16 |
boj)17103 - 골드바흐 파티션 (0) | 2020.09.16 |