백준 11726번 2xn 타일링 Java (☆공부 260일차)

11726 2Xn 타일링

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

11726번: 2×n 타일링

 

 

 

 

---

백준 11726번 문제 2Xn 타일링

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	139906	53579	39624	36.192%

문제

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

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

입력

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

출력

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

제한

 

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/238

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

4달 전에 푼 문제 (오랜만에 공책 꺼내서 풀었다)

 

 

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

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

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

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

 

이에 따라 점화식은 다음과 같다

dp[i] = dp[i-2] + dp[i-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의 나머지를 구하라는 조건이 있나 궁금했는데, 찾아보니 오버플로우를 막기 위해서라고 한다

 

 

 

---

dp크기를 [n+1]으로 하고 n>1, n>2로 조건식 분기하는 것보다

그냥 dp[1001]로 하는 게 메모리를 생각했을 때 더 괜찮다