백준 11727번 2xn 타일링 2 Java (☆공부 261일차)

11727 2Xn 타일링 2

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

11727번: 2×n 타일링 2

 

 

 

 

---

백준 11727번 문제 2Xn 타일링 2

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	60895	36393	29154	59.164%

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

제한

 

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/240

공부 122일차: 백준 11727번 2Xn 타일링 2 자바 java

4달 전에 푼 문제

 

이전 풀이를 그대로 활용했다

 

점화식은 아래와 같다

dp[i] = dp[i-1] + 2 * dp[i-2]

 

 

 

---

정답 인정 코드

---

 

 

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[1_001];
        dp[1] = 1;
        dp[2] = 3;
        
        for(int i = 3; i < n+1; i++) {
            dp[i] = (dp[i-1] + 2 * dp[i-2]) % 10_007;
        }
 
        System.out.println(dp[n]);
        br.close();
    }
 
}

오버플로우 방지를 위해 % 10007 을 해줘야 한다

 

 

 

---

 br.close()를 추가한 것 말고는 이전 풀이와 다를 게 없다