[프로그래머스] 산 모양 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

코딩 테스트 준비를 위해 풀었지만 아무런 준비를 하지 못한 문제임

 

처음 문제를 접했을 땐 직관적으로 이전의 타일링 방식이 이후의 타일링 방식에 영향을 준다는 것을 알아채고 DP 문제라고 생각함

 

다만 DP의 점화식을 어떻게 구성할지에 대해서 고민하다가 풀지 못한 문제임, 처음부터 그림을 그리며 패턴을 파악했다면 그나마 유추할 수 있지 않을까 생각함

 

그 뒤로 gpt와 블로그 글을 참고하여 내용을 확인했지만 여전히 의문이 생겨 직접 그림을 그려 패턴을 파악하기로 함

top이 있고 없고의 모든 경우의 수

이 문제에서 중요한 케이스는 작은 단위의 타일에서 끝 타일이 채워지는 경우임, 이 경우는 다음 타일과 합쳐 계산할 때 영향을 주기 때문임

 

그림의 + 왼쪽에 위치한 타일의 끝 타일이 채워지지 않는 경우는 2, 끝 타일이 채워지는 경우는 1 임

 

그다음 타일이 top이 존재하지 않는 경우는

끝 타일이 채워지지 않는 경우의 수 = 이전 타일의 끝이 채워지지 않는 경우의 수 * 2 + 이전 타일의 끝이 채워지는 경우의 수(초록색 테두리)

끝 타일이 채워지는 경우의 수 = 이전 타일의 끝이 채워지지 않는 경우의 수 + 이전 타일의 끝이 채워지는 경우의 수 = 이전 타일의 모든 경우의 수(파란색 테두리)

 

특히 끝 타일이 채워지는 경우의 수는 현재 타일에서 끝이 채워지는 경우와 이전 타일의 모든 경우의 수가 합쳐질 수 있기 때문에 이전 타일의 모든 경우의 수라고 할 수 있음(파란색 테두리)

 

그다음 타일이 top이 존재하는 경우는

끝 타일이 채워지지 않는 경우의 수 = 이전 타일의 끝이 채워지지 않는 경우의 수 * 3 + 이전 타일의 끝이 채워지는 경우의 수(초록색 테두리) * 2

끝 타일이 채워지는 경우의 수 = 이전 타일의 끝이 채워지지 않는 경우의 수 + 이전 타일의 끝이 채워지는 경우의 수 = 이전 타일의 모든 경우의 수(파란색 테두리)

 

top이 존재하지 않을 때와 다른 부분은 끝 타일이 채워지지 않는 경우의 수를 세는 방법임, 다음 타일의 경우의 수가 하나 더 생겼기 때문에 3을 곱해주고 같은 이유로 이전 타일의 끝이 채워지는 경우의 수에서 곱하기 2를 해줌

 

따라서 다음과 같은 패턴을 보이기 때문에 dp에 저장될 값은 타일의 끝이 채워지지 않는 경우의 수와 끝이 채워지는 경우의 수임

dp = [끝이 채워지지 않는 경우의 수, 끝이 채워지는 경우의 수]

 

dp 배열의 첫 번째 값은 [1, 0]으로 설정해 주고 dp 배열의 길이는 n + 1 한 값으로 설정해 줌, 최종 결괏값은 dp의 n + 1번째 값의 합이 됨

 

문제에서 경우의 수를 10007 나눈 나머지 값을 구하는 것이기 때문에 다음 경우의 수는 나머지 값으로 계산함

 

문제를 풀면서 DP, 그리디 유형에서 직관적으로 파악하지 못하는 부분이 있는데 해당 유형을 더 풀어봐야 할 듯

 

DP문제에서 노가다를 하더라도 패턴을 파악하는 것이 중요한 것 같음

function solution(n, tops) {
    const dp = new Array(n + 1).fill().map(() => new Array(2).fill(0));

    dp[0][0] = 1;

    for (let i = 0; i < n; i += 1) {
        if (tops[i]) {
            dp[i + 1][0] = dp[i][0] * 3 + dp[i][1] * 2;
        } else {
            dp[i + 1][0] = dp[i][0] * 2 + dp[i][1] * 1;
        }

        dp[i + 1][1] = dp[i][0] + dp[i][1];

        dp[i + 1][0] %= 10007;
        dp[i + 1][1] %= 10007;   
    }

    return (dp[n][0] + dp[n][1]) % 10007;
}