산 모양 타일링(Java)

bearMin·2024년 4월 15일

🎯문제

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.

사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ n ≤ 100,000
tops의 길이 = n
- tops[i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.

입출력 예

n	tops	result
4	[1, 1, 0, 1]	149
2	[0, 1]	11
10	[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]	7704

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다. 문제에서 설명한 방법을 포함해 총 149가지 방법이 존재합니다.

따라서 149를 return 해야 합니다.

입출력 예 #2

문제 설명에 따라 만든 모양은 다음과 같습니다.

이 모양을 타일로 채우는 방법은 다음과 같이 총 11가지입니다.

따라서 11을 return 해야 합니다.

입출력 예 #3

경우의 수는 총 17,711가지입니다. 따라서 17711을 10007로 나눈 나머지인 7704를 return 해야 합니다.

✏️풀이

코드

class Solution {
    public int solution(int n, int[] tops) {
    	// 경우의 수에 따라 나뉘어진 배열
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        
        // 초깃값 설정
        a[1] = 1;
        b[1] = tops[0] == 1 ? 3 : 2;
        
        for(int i = 2; i <= n; i++) {
        	// a의 점화식 = a[i] = a[i-1] + b[i-1]
            a[i] = (a[i-1] + b[i-1]) % 10007;
            // b의 점화식
            // 1) 정삼각형이 위에 붙은 경우 => b[i] = 2 * a[i-1] + 3 * b[i-1]
            // 2) 정상각형이 위에 붙지 않은 경우 => b[i] = a[i-1] + 2 * b[i-1]
            b[i] = tops[i-1] == 1 ? (a[i-1] * 2 + b[i-1] * 3) % 10007 : (a[i-1] + b[i-1] * 2) % 10007;
        }
        
        return (a[n] + b[n]) % 10007;
    }
}

설명

dp의 방식을 사용하여 진행하였다.

정삼각형의 타일을 덮는 방법은 총 4가지이다.

위쪽 삼각형과 함께 마름모 타일로 덮기
왼쪽 삼각형과 함께 마름모 타일로 덮기
오른쪽 삼각형과 함께 마름모 타일로 덮기
정삼각형 타일로 덮기

가장 왼쪽 아래 정삼각형부터 시작하여 하나씩 타일을 덮는 방법을 결정해나간다.

a 배열은 i번째 아래 방향 정삼각형까지 덮되, i번째 아래 방향 정삼각형을 덮는 방법이 3번이 경우의 수이다.
b 배열은 i번째 아래 방향 정삼각형까지 덮되, i번쨰 아래 방향 정삼각형을 덮는 방법이 3번이 아닌 경우의 수이다.

이때 case는 2개로 나눌 수 있다.

case 1번은 i번째 아래 방향 정삼각형 위에 정삼각형이 붙은 경우이다.
이 경우에 a[i]는 a[i-1] + b[i-1]이다. 이전에 어떤 방식으로 덮었든 3번의 방식으로 무조건 덮을 수 있기 때문이다.
b[i]는 a[i-1]의 경우 1번과 4번의 방식을, b[i-1]의 경우 1, 2, 4번의 방식을 사용해서 덮을 수 있다. 따라서 2 a[i-1] + 3 b[i-1]이 된다.

case 2번은 i번째 아래 방향 정삼각형 위에 정삼각형이 붙지 않은 경우이다. 이 경우 마찬가지로 a[i]는 a[i-1] + b[i-1]이다. 3번의 방식으로 무조건 덮을 수 있기 때문이다.
b[i]는 a[i-1]의 경우 하나만 b[i-1]의 경우 2가지의 방법이 있으며 이를 식으로 풀면 a[i-1] + 2 * b[i-1]이 된다.

이때 초깃값은 a[1] = 1, b[1]은 정삼각형이 위에 붙은 경우에는 3, 그렇지 않은 경우에는 2로 설정을 해준다.

이후 위에서 구한 점화식을 활용하여 반복문을 진행하고 모든 반복이 끝난 뒤에 a[n] + b[n]을 10007로 나눈 나머지를 반환해주면 문제를 해결할 수 있다!

💡느낀 점

dp의 방식을 사용해서 풀었지만 경우의 수를 나누고 또 다른 여러 경우들을 생각해야하는 부분들이 많아서 매우 헷갈리고 어려웠다. 카카오 인턴쉽 문제라 그런가 확실히 쉽지 않았다.. 아직까지도 코드를 완벽하게 이해하고 있다는 생각이 들지 않아서 조금 더 다른 풀이 블로그들을 살펴보면서 제대로 이해를 해보는 시간을 가져야할 것 같다..!