프로그래머스 - 2 x n 타일링 (C++)

 

가로 길이가 n으로 주어질 때, 가능한 경우의 수는 몇개인가? 를 구하는 문제이다.

예를 들어 n이 3이라고 가정해보자.

이런 3개의 경우의 수가 가능할 것이다.

 

 n개일 때는 경우의 수가 몇개인지를 구하려면 어떻게 해야할까?

---

문제 풀이

이 문제는 기본적인 DP문제이다. 사실 DP문제는 어떠한 알고리즘이 있다기보단, 창의력이나 사고력을 요하는 경우가 더 많은 것 같다. 하지만, 자주 나오는 유형들을 보면 대부분 점화식을 이용하여 다음 항을 유추하는 케이스와 완전탐색과 함께 사용하는 케이스가 가장 많은 것 같다. 자주 풀어보면 감이 올 것이다.

 

이 문제는 먼저 점화식을 세워야 한다.

먼저, n개의 타일을 배치하는 여러 개의 경우의 수가 있다고 했을 때 모든 경우의 수를 고려하는 것이 아니라 딱 2개의 경우로만 나눠보자.

 

크게 두 개의 경우로 나누어 보자.

 

1. 맨 앞의 블럭이 서있는 경우

2. 맨 앞의 블럭이 누워있는 경우

 

맨 앞의 블럭이 서있는 경우와 맨 앞의 블럭이 누워있는 경우중 서로 겹치는 경우가 있을까?

절대 없을 것이다. 앞의 블럭 모양이 다르기 때문이다.

 

그렇기 때문에, N개의 줄에 타일을 배치하는 경우의 수는 맨 앞의 타일 이 서있는 경우 + 맨 앞의 타일 이 누워있는 경우로 바꿔서 생각해볼 수 있다.

 

N개의 줄에 타일을 배치하는 경우의 수  = 맨 앞의 타일이 서있는 경우 + 맨 앞의 타일 이 누워있는 경우

 

그렇다면, 두 개의 경우를 하나씩 살펴보자.

 

맨 앞의 타일 이 서있는 경우라면, 맨 앞의 타일 은 고정이기 때문에 뒤의 N-1줄에 타일을 배치하는 경우의 수가

곧 타일을 배치하는 전체 경우의 수이다.

 

즉 맨 앞의 타일 이 서있는 경우의 수는 N-1줄에 타일 을 배치하는 경우의 수이다.

 

N개의 줄에서 맨 앞의 블럭이 서있는 경우의 수  = N-1 줄에 타일을 배치하는 경우의 수

 

이번엔, 두 번째 경우를 보자.

 

맨 앞의 타일이 누워있는 경우이다. 타일이 누워있다면 총 두 줄을 점유하기 때문에, 뒤의 N-2줄에 타일을 배치하는 경우가 곧 타일을 배치하는 경우의 수가 된다.

 

N개의 줄에서 맨 앞의 블럭이 누워있는 경우의 수  = N-2 줄에 타일을 배치하는 경우의 수

 

이제, 맨 위에서 처음으로 구했던 명제를 보자.

 

N개의 줄에 타일을 배치하는 경우의 수 

= 맨 앞의 타일이 서있는 경우 + 맨 앞의 타일 이 누워있는 경우

=  N-1 줄에 타일을 배치하는 경우의 수 + N-2 줄에 타일을 배치하는 경우의 수

 

이런 결론에 도달할 수 있다.

 

우리는 직접 계산을 통해, N이 1, 2, 3 일 때의 경우의 수는 쉽게 구할 수 있다.

D(N) 이 N개의 줄에 타일을 배치하는 경우의 수라면,

 

D(1) = 1;

D(2) = 2;

D(3) = 3;

 

이렇게 될 것이다.

 

이제부터 반복문을 돌며 값을 구하면 된다.

 

D(4) = D(3) + D(2)

D(5) = D(4) + D(3)

           .

           .

           .

           .

 

D(N) = D(N - 1) + D(N - 2) 까지 답을 구하면 문제는 끝난다.

---

풀이 코드

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) 
{  
    std::vector<int> DP(n + 1, 0);
    
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 3;
    
    int CurIndex = 4;
    int EndINdex = n;
    
    while(CurIndex <= n)
    {
        DP[CurIndex] = (DP[CurIndex - 1]  + DP[CurIndex - 2]) % 1000000007;       
        CurIndex++;
    }
    
    return DP[n];
}

 

풀이는 정말 간단하다.

위에서 구했던 점화식을 그대로 코드로 작성하면 된다.

 

코드를 짜는게 어렵다기보단, 아이디어를 떠올리는게 다소 어려울 수 있었던 문제이다.

 

결과