[c++ | 백준] 11726번 2 x n 타일링

c++ 문제 풀이

 

 

 

 

 

---

 

 

[백준 11726번 2 x n 타일링 문제]

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

 

 

 

 

---

 

 

 

전체 풀이 코드

#include <iostream>
using namespace std;

long long dp[1001] = { 0,1,2};
long long DP(long long n)
{
    if (n <= 2 || dp[n] != 0) return dp[n] ;
    dp[n] = (DP(n - 1) + DP(n - 2)) % 10007;
    return dp[n];
}

int main(void)
{   
    int n;
    cin >> n;
    cout << DP(n);

    return 0;
}

 

 

 

풀이 설명

 

1. 전역 변수

// dp로 구한 값을 저장하는 배열
long long dp[1001] = { 0,1,2};

 

 

이제 부터 DP 문제를 풀어볼겁니다. main 함수 부터 설명드리도록 하겠습니다.

 

 

2. main 함수

int main(void)
{   
    int n;
    cin >> n;
    cout << DP(n);

    return 0;
}

2 x n의 공간을 채워야 하는 타일의 개수를 10007로 나눈 나머지를 구해야 하기 때문에 n을 입력받은 후 DP함수에 넘겨줄 겁니다. 

 

DP함수에서 얻은 정답을 출력해주면 main함수는 끝입니다.

 

 

3. DP 함수

DP는 전에 구해놨던 값들을 통해서 현재의 답을 구하는 방법입니다. 따라서 전 값들을 저장하기 위해 dp배열을 만들어 둔 것입니다.

 

우리는 타일의 개수를 구하기 위해서 타일을 어떻게 배치할 것인지 생각해 보아야 합니다.

 

 

타일을 놓을 수 있는 방법은 세로로 1개를 놓고 시작하는 방법, 가로로 2개를 놓고 시작하는 방법 2가지가 있습니다. 따라서 첫 번째 방법의 모든 방법 + 두 번째 방법의 모든 방법을 해준다면 현재의 방법의 개수를 알 수 있을 겁니다.

 

첫 번째 방법을 봅시다.

첫 번째 방법의 타일의 가로의 길이는 1입니다. 따라서 첫 번째의 모든 방법의 수는 dp[n-1]의 값일 겁니다.

 

두 번째 방법을 봅시다.

두 번째 방법의 타일의 가로 길이는 2입니다. 따라서 두 번째의 모든 방법을 수는 dp[n-2]의 값일 겁니다.

 

이해가 되지 않는다면 예시를 들어 설명드리겠습니다.

 

n이 3일 때 타일을 놓을수 있는 방법을 구해봅시다.

 

먼저 타일을 세로로 1개 놓는 방법을 사용한다면 2가지의 방법이 나오게 됩니다.

 

다음으로 타일을 가로로 2개 놓는 방법을 사용한다면 1가지의 방법이 나오게 됩니다.

 

 

따라서 여기서 규칙이 보이게 됩니다. n-1(n=2)의 방법의 수와 n-2(n=1)의 방법의 수를 더한다면 우리가 구하려던 n=3일 때의 방법의 수가 나오는 것 입니다.

 

지금까지 얘기한 방법을 코드로 적어봅시다.

long long DP(long long n)
{
    if (n <= 2 || dp[n] != 0) return dp[n] ;
    dp[n] = (DP(n - 1) + DP(n - 2)) % 10007;
    return dp[n];
}

먼저 인덱스 0은 사용하지 않을 것입니다.

따라서 1번 인덱스의 값과 2번 인덱스의 값을 미리 구해 넣어놓을 것 인데, 그 이유는 n-2를 이용해서 값을 구할 것 이기 때문에 1번 인덱스 값과 2번 인덱스 값은 무조건 존재해야합니다.

 

if (n <= 2 || dp[n] != 0) return dp[n] ;

따라서 2보다 작은 dp배열의 값은 이미 구해져 있기 때문에 dp[n]을 그대로 리턴해줍니다.

또한 dp값이 0이 아니라면 이미 값을 구한 것이기 때문에 dp[n]을 그대로 리턴해줍니다.

 

dp[n] = (DP(n - 1) + DP(n - 2)) % 10007;
return dp[n];

위 if문에 걸리지 않았다면 구해진 dp값이 없다는 것이기 때문에 dp값을 구해줄 겁니다.

dp값은 위에서 설명한 것 처럼 dp[n-1] + dp[n-2]이기 때문에 DP함수를 불러 값을 구해줄 겁니다.

 

또한 문제 조건에 10007로 나눈 나머지를 출력하라고 되어있기 때문에 나누기 10007을 한 값을 dp[n]에 저장해주고 리턴해줍니다.

---

 

이렇게 백준 11726번 문제를 DP로 풀이해보았습니다.

궁금한점 있으시면 댓글 남겨주세요!