백준 11726번 2xn 타일링 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

128307

48836

36026

35.916%

문제

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

 

 

풀이

다이나믹 프로그래밍 문제들은 대부분 문제에 힌트가 적혀있다.

해당 문제는 2일때의 가지수와 9일때의 가지수를 제시해주고 있다.

보통은 동적계획법 문제들은 문제에서 원하는것처럼 몇가지의 방법이 존재하는지를 직접 구하라는게 아닌

 

일정한 패턴으로 반복되는 문제의 패턴을 내가 찾아내고, 진짜 말 그대로 어떠한걸 직접 구하라는게 아닌 답만 구해오면 되는 문제들이 대부분인것 같다.

 

마찬가지로 해당 문제 또한 1000까지의 숫자가 제시된다고 나와있으니 1001의 인덱스를 가진 배열을 생성해준다. (1부터 순회할것이기 떄문)

 

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];

 

그리고 문제의 첫부분에 내가 직접 구할 수 있는 답들은 미리 구해본다.

 

문제에 일정한 패턴이 존재하는지를 알아보는것이다.

N 이 1일때, 단순 2X1 의 직사각형 하나만 들어가기때문에 1이된다.

N 이 2일때는 문제에서 답을 알려주고있으니 2가 되고,

N 이 3일때는 직사각형이 세로로 3개, 가로로 두개 세로로 하나, 직전의 배치를 반전시킨 모습 이렇게 3가 된다.

 

어? 벌써 뭔가 패턴이 그려진다.

바로 N-2 + N-1 의 값이 N의 가짓수가 될 수 있다는 말이다.

마찬가지로 N이 4일때의 가짓수를 직접 구해본다면 5가 나올것이다.

 

고러취~ 하고 바로 반복문으로 4부터 돌려준다.

 

        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=N;i++){
            dp[i]= (dp[i-2]+dp[i-1])%10007;
        }
        System.out.println(dp[N]);

그냥 아예 답에선 10007으로 나눴을때의 나머지를 구해오라고 했기 때문에 답도 그렇게 넣어준다.

 

너무 짧은 코드로 깔끔하게 풀리는 문제이다.