[백준] 11726 - 2xn 타일링 자바

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.


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

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

접근방법

  N의 개수가 늘어날수록, 만들 수 있는 조합의 수가 증가한다. 그러나  n이 2칸 증가할 때와 1칸 증가할 때,  만들 수 있는 경우의 수가 달라진다. 그렇기에 어떤 규칙성을 만들 수 있을까부터 생각해야 한다. 규칙성이 잘 보이지 않아, 그려가며 접근했고, 이전 값들을 활용해서 현재 값을 확인할 수 있는 방법을 찾아냈다. 즉, DP(Dynamic Programming) 문제이다.

 

풀이

 N = 1 일 때는 세로 한칸의 방식밖에 사용할 수 없다. 그러나 N= 2가 되면 세로로 두 칸 가로로 두 칸으로 방법의 가짓수가 2개가 된다.

그런데 N = 3일때 부터 보자. 2 x 3에서 블록을 둘 때, 뒤에서 부터 생각하면 모든 경우의 수는 두 가지로 나뉘게 된다.

 

1. 마지막 블록이 세로 블록이다.
2. 마지막 블록이 가로 블록이다.

 

1번의 경우, 이전값에서 블록 하나만 맨뒤에 붙인 것으므로, N= k 일 때 k-1 값만 더 해주면 된다.

2번의 경우, 칸을 2블록을 차지한다. 때문에  N= k 일 때, k-2 값을 더 해줘야 한다.

위의 경우를 N =3 일 때에 대입하여, 그림으로 표현해보았다.

 

결국 뒤쪽 블록이 어떤 형태이냐만 나누어준다면, 이전 값을 활용하여, 새로운 값을 도출해 나갈 수 있다.

 

 

즉, DP [N]을 2 x N에서 블록을 놓을 수 있는 경우의 수라 가정했을 때, 다음과 같이 표현할 수 있다.

 

DP [k] = DP [k-1]+DP [k-2]

 

위의 원리를 이용하여, 코드에 대입하면 다음과 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        Main tset =new Main();
    }

    int[] dp = new int[1001];
    public Main() throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        System.out.println(solution(num));

    }

    int solution(int num){

        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3 ; i <dp.length;i++){
            dp[i] = (dp[i-1]+dp[i-2])%10007;


        }
        return dp[num];
    }
}

결과

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.