[프로그래머스] 동적 프로그래밍(Dynamic Programming), 타일 문제

안녕하세요. 오늘은 프로그래머스 레벨 1 중에서 동적 프로그래밍 문제를 가져왔습니다.

 

 

저는 다이나믹 프로그래밍을 배우기는 했지만 까먹었던 터라 이 문제를 해결하는 것이 꽤나 어려웠습니다.

하지만 여태 프로그래밍 문제를 좀 풀어본 내공을 활용해서, n의 케이스를 나눠 n번째 경우의 수를 n에 관한 다항식으로 표현하려고 했어요.

 

 

저의 시도들!

 

저는 이 문제를 중복 순열처럼 접근했던 거 같습니다. 왜냐하면 각 타일마다 종류와 순서가 구분되었고.

그리고 n=4일때 예제에서 길이가 2인 타일과, 4일때 패턴이 상이하기 때문이었어요.

 

실제로 길이가 4 이상일 때만 만들 수 있는 독특한 패턴이 있어서. 각각 2n과 4n으로 정의했습니다.

 

2n인 경우에는 타일이 3가지가 있으니, 3개의 타일을 배치하는 경우의 수니까 3*3*3... = 3**n이라고 생각했어요.

그리고 나머지 4개짜리 타일 패턴이 0개~ 최대 n/4개가 있을테니까, 각각의 경우에 경우의 수를 일반항으로 만들었습니다.

 

이렇게 쓰고 나니 이항정리처럼 되는 거 같아 전체 sum을 이항정리를 이용해서 (2+3)^(n/4 ...) 형태로 정리한 뒤에, 중복되는 첫항 (q=0, 2n만 있는 경우)을 빼서  길이가 n인 타일을 채우는 경우의 수의 일반항을 정의했습니다.

  

그런데 아마 수식을 정의하는 과정에서 논리적인 오류가 있었던 거 같아요.

나중에 살펴보니 6n짜리 타일도 있더군요. 그래서 아 이 방식대로 구하면 문제가 너무 커지겠다고 생각했습니다.

그리고 고민한지 약 30분~1시간이 넘어가던 타이밍이라. 해당 문제의 힌트를 얻기로 했어요.

 

1차 학습: 구글링 티스토리 검색

 

https://kne-coding.tistory.com/327

[프로그래머스/Python] 3 x n 타일링

 

티스토리에서 풀이를 확인했는데, 정답이라고 하지만 납득하기가 어려웠습니다.

왜냐면 일단 이해가 잘 되지 않았어요.

 

피보나치 수열처럼 점화식으로 이전 항을 이용해 n번째를 계산하는 것 까지는 이해했는데,

n-1번째와 n번째 항 사이의 점화식이 이해가 되지 않았습니다.

그래서 Dynamic programming에 대한 추가 학습이 필요하다고 생각했어요.

 

2차 학습: 유튜브 Dynamic programming, tiling example 학습

 

https://www.youtube.com/watch?v=yn2jnmlepY8

 

프로그래머스에서 만나는 문제들은 낯설지만, Dynamic programming 분야에서 Tiling example은 굉장히 유명한 거 같았습니다. 다룬 영상들도 많아서, 가시성이 좋은 자료로 골랐어요.

 

 영상과 tistory를 비교하자면, n-1번째를 이용해서 n번째를 구하는 방식은 동일하나 n-1번째의 상태를 정의하는 방식이 다릅니다.

 

 

저는 사실상 DP(Dynamic programming)을 다 까먹어서, 영상을 다 보고 나서야 어느정도 이해할 수 있었어요.

핵심은 Column 1개의 모든 경우의 수를 정의하고, 이전의 n-1번째 까지 '완성된' 타일에 2x1 타일을 더해 n번째 상태를 만든다는 것이었어요.

 

 

영상에서 설명하듯이,  DP의 경우 보통 점화식을 찾으려고 하는데, 이 점화식을 찾기가 굉장히 어려운 경우가 타일 문제 같은 경우입니다. n=4만 되도 11개고, 5개나 6개가 되면 더 복잡해지고, 뭣보다 케이스를 일일히 손으로 그려서 찾아야 하니 어렵다는 뜻이었어요.

 

 

그래서 역으로, n번째 타일을 빈틈없이 채우는 케이스를 만들기 위한, n-1의 상태를 추적합니다.

지금 사진에서는 n=2까지는 빈틈없이 차 있고, n=3일때 타일을 하나 채워서 완성한 케이스에요.

n=2인 상황에서도 3번째 타일이 삐죽 튀어나와 있지만, 이렇게 부분적으로 튀어나온 케이스도 하나의 state로 보겠다는 접근입니다. 저는 이게 좀 특이했던 거 같아요.

 

문제 예시에서도 보면 타일이 꽉 찬 예시만 보여주지, 빈틈이 있는 타일을 예시로 보여주지 않으니까요.

 

 

그래서 '빈틈이 있는' 케이스를 포함해서, n-1번째 컬럼에 있을 수 있는 모~든 타일의 배치 경우의 수를 다음과 같이 정의합니다. 확률 통계로 치면 Sample Space를 정의하는 과정이에요. {0,1,2,3,4,5,6,7} 이외의 경우의 수는 일어날 수 없다!는거죠. 

 

 

가장 어려운 과정은 이 둘 사이의 관계를 찾는 일이었어요.

음.. 8개 경우에 대해 모두 구해야하는 것은 사실인데. 1개만 이해해도 나머지는 거의 같은 방식으로 동작해요.

 

 

예를 들어, 지금 i번째 타일 상황이 1번이죠. 그러면 dp[i][1]이라고 정의할게요.

dp[i][1]을 만들려면, dp[i-1][?] 에서 ?는 무엇이어야 할까요?

i-1은 i 보다 한 단계 이전의 컬럼을 말해요.

 

 

정답은 6번입니다. 6번에 보면 맨 위쪽 셀이 비어있죠. 여기다가 2x1을 놓으면 i번째에서 1번 타일의 모양이 되니까,
dp [i-1][6]번 타일을 만드는 모든 경우를 dp[i][1]에 더해주면 돼요.

이때 dp[i][1]=dp[i-1][6]으로 하지 않는 경우는, 후술하겠지만 꼭 한 개의 상태에서만 다른 상태로 전이되는 게 아니기 때문이에요.

 

그러니까 6번 이외 다른 상태에서도 1번으로 전이될 수 있기 때문에, 전이 가능한 모든 경우의 수를 합해주는 겁니다.

예를들어 6번 상태를 만들기 위해서는, 1번에서 2x1을 두 개 놓는 방법도 있지만,

완성된 7번에다 세로로 1x2 타일을 놓는 방법도 있기 때문에 둘 다 더하는거에요.

더하는 이유는 서로가 타일 배치가 중복되지 않는 유니크한 사건이기 때문이죠.

 

 

이 방식대로 더하다보면,

 

dp[n][7]에는, 길이가 n*3인 타일을 빈틈없이 메우는 경우의 수가 모이게 됩니다.

 

솔루션 코드

    int answer = 0;
    long dp[5000][8] = {0};

 

아이디어는 모두 얻었으니 구현을 시작했어요. 영상에서는 파이썬으로 코드가 만들어져 있어서, 저는 c++로 옮겨봤습니다.

 

주의해야할 점은.

1.  2차원 배열을 초기화 해야함.

2.  타입을 int가 아닌 long을 사용해야함.

 

1번은 초기화 하지 않으면, dp[0][..]의 값들에 garbage value라고 하나요? 정해지지 않은 쓰레기 값이 들어가게 돼요.

그래서 디버깅해보면 -816268248 같은 이상한 숫자들이 경우의 수에 더해져서 값이 틀립니다.

 

2번은 좀 어려웠는데. 문제 힌트 중에 % 10000007로 나누라는 것이 힌트가 있어요.

값이 굉장히 크기 때문에 이 연산을 하겠다는 것은 알겠는데, 왜 이 숫자로 나누는 것일까에 대한 궁금증은 있었거든요.

 

알고보니 이 수가 소수였습니다. 그래서 1 이외에 나눠지는 수가 없었고, mod를 하게 되면 이 수 보다 작은 수는 그대로 나오고, 큰 수인 경우에는 이 수를 뺀 나머지 값이 유니크하게 나올 테니까, 일종의 수의 크기가 int 범위를 벗어나는 것을 막아주는 역할을 해요.

 

여기서 부터는 제 추측이지만, long은 int(2^32)보다 비트수가 2배 많은(2^64) 숫자 범위를 표현할 수 있지만,

n=5000에 가까워지면 더하는 수들이 너무 커져서 long의 범위도 벗어나게 되는 거 같습니다.

그래서 1차로 mod 연산으로 더하는 숫자의 크기를 줄이고. 크기가 큰 container를 사용한 거 같아요.

 

프로그래머스에서는 int를 사용했을 때 에러가 발생했습니다.

그 원인을 찾기 위해 visual studio에서 n=5000일때를 디버깅 해보니

 

[5000][..]가 아니라 [1][..] 의 값을 바꾸고 있었습니다.

그래서 이 이유가 뭘까 좀 고민하고 있습니다.

일단은 프로그래머스 기준 통과한 코드는 아래와 같고,

int를 사용했을때 n=5000으로 계산한 값이 오류인지 아닌지는 추후에 확인해보겠습니다.

혹시나 아시는 분이 있으시다면! 댓글로 알려주시면 감사하겠습니다 :))

 

똑똑한 사람은 언제나 환영이야~

 

int solution(int n) {
    int answer = 0;

    long dp[5000][8] = {0};


    dp[0][7] = 1;
    for (int i = 1; i < n + 1; i++)
    {
        dp[i][0] += dp[i - 1][7];

        dp[i][1] += dp[i - 1][6];

        //dp[i][2]+=dp[i-1][5];

        dp[i][3] += dp[i - 1][4];
        dp[i][3] += dp[i - 1][7];

        dp[i][4] += dp[i - 1][3];

        //dp[i][5]+=dp[i-1][2];

        dp[i][6] += dp[i - 1][1];
        dp[i][6] += dp[i - 1][7];

        dp[i][7] += dp[i - 1][0];
        dp[i][7] += dp[i - 1][6];

        dp[i][7] += dp[i - 1][3];
        dp[i][7] = dp[i][7] % 1000000007;
    }

    

    cout << dp[n][7] << endl;
   
    return dp[n][7];


}