[Java] 산 모양 타일

프로그래머스

 

문제 풀이

주어진 n 과 tops로 인해 형성되는 모양을 4가지 모양의 도형으로 채울 수 있는 "경우의 수"를 구하는 문제이다. 문제를 보자마자 규칙을 찾아야 겠다는 생각이 들었다. 다행히 직관이 잘 얻어 걸렸던 것 같다. 

 

우선 4가지 모양의 도형의 유형과 n과 tops로 형성되는 모양 간의 규칙에 집중했다. 채워야할 공간의 n번째 사다리꼴에서 가운데 뒤집어진 삼각형을 기준으로 아래 4가지 모양을 사용해서 채울 수 있다.

 

4가지 모양

1. 윗 정삼각형과 함께 덮여지는 마름모

2. 왼 정삼각형과 함께 덮여지는 마름모

3. 오른 정삼각형과 함께 덮여지는 마름모

4. 하나의 정삼각형

 

다음으로는 현재 k번째라고 했을 때 k-1 번째와의 관계를 살펴봤다.

만약 윗 삼각형이 k번째 삼각형 위에 놓여있고 k-1 번째 삼각형이 3번의 방식으로 놓여있다면

k 번째는 1, 3, 4 만 가능하고, 그렇지 않다면 1, 2, 4가 가능하다. 

 

만약 윗 삼각형이 없고 k-1 번째 삼각형이 3번의 방식으로 놓여있다면

k 번째는 3, 4만 가능하고 그렇지 않다면 2, 3, 4가 가능하다.

 

이렇게 정리하고 보면 3번 모양을 쓰냐 안쓰냐에 따라서 겹쳐지는 부분에 의해 다음 경우의 수가 결정이 된다.

그래서 k번째 삼각형을 3번으로 채워진 경우의 수를 기록하는 A[], 그렇지 않은 B[] 두개를 만들면 다음과 같은 점화식을 세울 수 있다.

 

C1 - (tops[k - 1] == 1) 윗 삼각형이 있는 경우

A[k] = A[k - 1] + B[k - 1]

B[k] = 2 * A[k - 1] + 3 * B[k - 1]

 

C2 - (tops[k - 1] == 0) 윗 삼각형이 없는 경우

A[k] = A[k - 1] + B[k - 1]

B[k] = A[k - 1] + 2 * B[k - 1]

 

모든 과정들에 MOD(10,007)의 나머지로 저장해주고 마지막 정답은 A[n] + B[n]을 구해주면 정답이 된다.

 

class Solution {
    final int MOD = 10_007;
    public int solution(int n, int[] tops) {
        int answer = 0;
        
        int[] A = new int[n + 1];
        int[] B = new int[n + 1];
        
        A[0] = 0;
        B[0] = 1;
        
        for (int i = 1; i < n + 1; i++) {
            if (tops[i - 1] == 1) {
                A[i] = (A[i - 1] + B[i - 1]) % MOD;
                B[i] = (2 * A[i - 1] + 3 * B[i - 1]) % MOD;
            } else {
                A[i] = (A[i - 1] + B[i - 1]) % MOD;
                B[i] = (A[i - 1] + 2 * B[i - 1]) % MOD;
            }
        }
        
        answer = (A[n] + B[n]) % MOD;
        return answer;
    }
}