ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 10-6: 직사각형 배치의 경우의 수
    DP 2018. 10. 25. 21:48

    직사각형 배치의 경우의 수

     

    문제


    2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

    예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.

    alt text

     

    입력


    첫 번째 줄에 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
Designed by Tistory.