https://www.acmicpc.net/problem/11727
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
내 풀이
2*1 , 1*2 , 2*2 타일로 채우는 방법의 수를 찾는 것 고로
2*n 블럭 만드는 경우의 수를 2* n-2 블럭에서 만드는 경우와 2* n-1 블럭에서 만드는 경우를 고려하여 dp를 만들었다.
그것을 수식으로
DP[n] = DP[n-1] + 2 * DP[n-2] 로 만들 수 있었다.
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
//static StringBuilder output = new StringBuilder();
public static void main(String arg[]) throws IOException {
Scanner sc= new Scanner(System.in);
int input= sc.nextInt();
long[] DP=new long[1001];
DP[1]=1;
DP[2]=3;
for(int i=3;i<=input;i++) {
DP[i]=(DP[i-1]+2*DP[i-2])%10007;
}
System.out.print(DP[input]%10007);
}
}
반응형
'TIL > SW&백준 문제 리뷰' 카테고리의 다른 글
[백준] 1931 회의실 배정 (0) | 2021.08.09 |
---|---|
[백준] 2309 일곱 난쟁이 (0) | 2021.08.05 |
[백준] 11053 가장 긴 증가하는 부분 수열 (0) | 2021.07.29 |
[백준] 11052 카드 구매하기 (0) | 2021.07.28 |
[백준] 9663 N-Queen (0) | 2021.07.22 |
댓글