[백준] 자바 11727 2xn 타일링 2

[백준] 자바 11727 2xn 타일링 2

문제

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

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

2*17

입력

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

출력

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

테스트 케이스

입력 1

501

출력 1

4172

입력 2

1

출력 2

1

입력 3

1000

출력 3

7326

접근

코드 자체는 간단하지만 dp문제이므로 규칙 찾는 게 핵심인 문제인 듯합니다.

1.2*n 식에 들어갈 n을 입력받습니다.

1

일단 n이 몇이든간에, 시작은 그림과 같이 3가지 경우로 블록은 쌓이면서 시작합니다.(n이 1일 때만 제외하고)

2

n이 1일때랑, 2일 때의 개수를 직접 세보았습니다.

3

f(3)부터는 규칙이보이게됩니다.

첫 사진에 설명한 것처럼 3가지 경우로 시작할 수밖에 없는데, 3가지 경우로 시작한 경우 남는 블록수만큼 f(n)을 지정하여 더해주면 됩니다.

따라서 f(n) = f(n-1) + 2*f(n-2)라는 점화식이 나오게 됩니다.

이를 이용하여 코드를 짜니 문제가 해결되었습니다.

코드

import java.awt.desktop.SystemEventListener; import java.io.*; import java.math.*; import java.util.*; public class Main { /* 11727 problem */ public static void main(String[] args) throws NumberFormatException, IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int num = Integer.parseInt(br.readLine()); ArrayList list = new ArrayList<>(); list.add(1); list.add(1); for(int i=2; i<=num; i++) { list.add((list.get(i-1) + 2*list.get(i-2))%10007); } bw.write(String.valueOf(list.get(num))); bw.flush(); br.close(); bw.close(); } }

주의

10007로 나눠서 출력해주는 것 주의.

728x90

반응형

from http://kjs-dev.tistory.com/135 by ccl(A) rewrite - 2021-09-21 13:27:40