공부 121일차: 백준 11726번 2Xn 타일링 자바 java

11726 2Xn 타일링

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

11726번: 2×n 타일링

 

 

 

 

---

백준 11726번 문제 2Xn 타일링

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

 

동적 계획법은 직접 그려보면서 규칙을 찾아내는 게 핵심인 듯하다

손으론 2x6까지도 그렸는데 어차피 규칙만 찾으면 돼서 2~4까지만 컴퓨터로 그려봤다

6까지 그려보면 2부터 6까지 2, 3, 5, 8, 13이 나온다

-2를 한 값과 -1을 한 값을 더했음을 알 수 있다

도형의 특성으로 보자면 눕거나 세운 도형을 기본으로 양옆이나 가운데에 하나씩 더해가면서 그 숫자를 더한다고 볼 수 있다

 

 

 

---

정답 인정 코드

---

 

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

 

문제에 왜 10007의 나머지를 구하라는 조건이 있나 궁금했는데, 찾아보니 오버플로우를 막기 위해서라고 한다

 

 

 

---