-
10-6: 직사각형 배치의 경우의 수DP 2018. 10. 25. 21:48
직사각형 배치의 경우의 수
문제
2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.
예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.
입력
첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )
출력
가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.
예제 입력
3
예제 출력
3
예제 입력
8
예제 출력
34
예제 입력
37
예제 출력
87896
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class dp_rect_placement {
/**
* 직사각형 배치의 경우의 수
*
*
* 문제
* 2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.
*
* 예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.
*
* 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )
*
* 출력:
* 가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.
*
* 예제 입력:
*
* 8
*
*
* 예제 출력:
* 34
*
*
* 37
* 87896
*
* @param args
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int dp[] = new int[N+1];
dp[1] = 1;
dp[2] = 2;
for (int i=3; i<N+1; i++){
dp[i] = dp[i-1] + dp[i-2];
dp[i] %= 1000007;
}
System.out.println(dp[N]);
}
}'DP' 카테고리의 다른 글
10-8: 자원채취 (0) 2018.10.25 10-7: 제곱수의 합 (0) 2018.10.25 10-5: 버튼 누르기 (0) 2018.10.25 10-4: 카드 놀이 (0) 2018.10.25 10-3: 구슬 게임 (0) 2018.10.25