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

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

접근

전형적인 DP 문제다.

$n$ 을 점점 늘려 최종 결과를 산출하는 과정에서 $n-1$ 과 $n$ 에서의 연산 결과의 연관성을 찾으면 된다.

일단 $n=1$ 일 때는 경우의 수가 $4$ 임을 쉽게 알 수 있다. 윗 변에 공유하는 정삼각형이 없는 경우의 수는 $3$ 이다.

$n=2$ 이고 윗 변에 공유하는 정삼각형이 있는 있는 경우를 확인해보자.

$n=1$ 의 결과에서 새로운 영역(빨간색 영역)의 경우의 수를 곱하는 경우의 수가 결과에 포함됨을 알 수 있다.

하지만, 이 새로운 영역이 추가됨에 따라 타일에 의해 공유하는 영역도 생겼다.

이 공유 영역(보라색 영역) 또한 고려해줘야 모든 경우의 수를 알아낼 수 있다.

이렇게 되면 $n=1$ 에서 재사용하게 되는 도형이 $n=2$ 에서의 공유 영역에 따라 각기 다르게 된다.

이는 다음 그림에서 흰 영역과 같다. 사진은 윗 변에 공유하는 정삼각형이 없는 형태를 예로 들었지만 핵심만 파악하면 된다.

이 두 경우밖에 없으므로 각 $n$ 에서 위 두 경우를 따로 저장해 재사용하면 된다.

추후 설명의 편의를 위해 첫 번째 경우를 A, 두 번째 경우를 B라고 하겠다.

그렇다면 윗 변에 공유하는 정삼각형이 없는 경우는 어떨까?

공유 영역에 대해서는 공유하는 정삼각형이 있는 경우와 동일하게 하나이고, 공유하지 않는 영역에 대해서는 공유하는 정삼각형이 있는 경우에서 하나 줄어들어 두 개이다.

memoization을 위한 dp[i][j] 배열의 정의에서 j 는 $0$ 과 $1$ 둘 밖에 없다. 정의는 다음과 같다.

dp[i][0] 은 n=i 인 사다리꼴에서 A가 되는 경우의 수이고,

dp[i][1] 은 n=i 인 사다리꼴에서 B가 되는 경우의 수이다.

소스코드(Java)

class Solution {
    public int solution(int n, int[] tops) {
        int[][] dp = new int[n][2];

        dp[0][0] = 2+tops[0];
        dp[0][1] = 3+tops[0];

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

        return dp[n-1][1];
    }
}

 

참고로 중간 연산에서 계속해서 10007을 나머지 연산하지 않으면 마지막으로 연산한 결과(큰 수)에 대해 오버플로우가 발생하여 나머지 연산을 한다고 하더라도 잘못된 결과가 나올 수 있음에 주의하자.