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

📘 문제 설명

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

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

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다

📘 요구 사항

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

📖 문제 해결 전략

• 타일을 채우는 문제는 꽤 자주 본 DP 문제라서 이 문제를 보자마자 점화식을 찾고자했다.
• 아래방향으로 뒤집어진 삼각형의 개수는 주어진 n 값과 같다. 마름모를 넣기 위해서는 반드시 이 뒤집어진 삼각형은 포함되므로 이것을 기준으로 점화식을 작성해보자.
• K번째 뒤집어진 삼각형을 채울 수 있는 방법은 4가지가 있다.
  1. 윗 삼각형과 이어진 마름모 채우기
  2. 왼쪽 아래 삼각형과 이어진 마름모 채우기
  3. 오른쪽 아래 삼각형과 이어진 마름모 채우기
  4. 그냥 정삼각형 채우기

  여기서, K-1번째 삼각형이 3번 방식으로 채워진 경우 그 다음 K번째 삼각형은 2번 방법으로 채워질 수 없다. 2번과 3번 방식이 다음 뒤집어진 삼각형 채우기에 영향을 주므로 3번으로 마름모를 채울 수 있는 경우의 수를 배열 a에, 1, 2, 4번으로 마름모를 채울 수 있는 경우의 수를 배열 b에 담아서 따로 점화식을 작성한다.

  • K번째에 윗삼각형이 붙는 경우, 즉 tops[K - 1] == 1 인 경우

    a[k] = a[k - 1] + b[k - 1]

    k번째에 오른쪽 아래 삼각형을 채우는 방법은 3번 하나뿐이니 전 결과를 단순히 더해주면 된다.

    b[k] = 2 * a[k - 1] + 3 * b[k - 1]

    k - 1번째에 3번 방법으로 채운 경우에는 1번과 4번 방법으로 채울 수 있고, 그렇지 않은 경우네는 1, 2, 4번 방법으로 채울 수 있으니 점화식이 위와 같이 나온다.

  • K번째에 윗삼각형이 없는 경우, 즉 tops[K - 1] == 0 인 경우

    a[k] = a[k - 1] + b[k - 1]

    k번째에 오른쪽 아래 삼각형을 채우는 방법은 똑같이 3번 하나 뿐이므로 점화식이 같다.

    b[k] = a[k - 1] + 2 * b[k - 1]

    이번 경우에는 윗 삼각형이 없으므로 1번 방법으로는 k번째 삼각형을 채울 수 없다. 따라서 곱하는 값이 1씩 줄어들었다.

  위의 내용을 함수로 구현하면 다음과 같다.

for(int i = 1; i < tops.length; i++) {
	if(tops[i] == 1) {
		int cnt = a.get(i - 1) + b.get(i - 1);
		a.add(cnt % 10007);
		cnt = 2 * a.get(i - 1) + 3 * b.get(i - 1);
		b.add(cnt % 10007);
	}
	else {
		int cnt = a.get(i - 1) + b.get(i - 1);
		a.add(cnt % 10007);
		cnt = a.get(i - 1) + 2 * b.get(i - 1);
		b.add(cnt % 10007);
	}
}

• 구하고자 하는 값이 10007로 모듈로 연산을 한 값이므로 결과값에 미리10007로 모듈로 연산을 해서 더해준다. 모듈로의 특성상 미리 계산을 적용해주어도 결과는 같으며, 이렇게 해주지 않으면 int의 범위를 넘어서서 결과가 달라질 수 있다.
• 구하고자 하는 값은 a, b 배열의 n번째 원소 값의 합이며, 마지막 결과에도 모듈로 연산을 적용해주어야 한다는 점을 잊으면 안된다.
• 초기값은 a[0] = 1 로 해주고, 윗삼각형이 있는지에 따라서, 즉 tops[0]이 1이면 b[0] = 3으로, 0이라면 b[0] = 2로 초기화해준다.

📖 전체 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] tops) {
        ArrayList<Integer> a = new ArrayList<>();
		ArrayList<Integer> b = new ArrayList<>();
		a.add(1);
		if(tops[0] == 1) {
			b.add(3);
		}
		else {
			b.add(2);
		}
		
		for(int i = 1; i < tops.length; i++) {
			if(tops[i] == 1) {
				int cnt = a.get(i - 1) + b.get(i - 1);
				a.add(cnt % 10007);
				cnt = 2 * a.get(i - 1) + 3 * b.get(i - 1);
				b.add(cnt % 10007);
			}
			else {
				int cnt = a.get(i - 1) + b.get(i - 1);
				a.add(cnt % 10007);
				cnt = a.get(i - 1) + 2 * b.get(i - 1);
				b.add(cnt % 10007);
			}
		}
		int answer = a.get(tops.length - 1) + b.get(tops.length - 1);
		return answer % 10007;
		
    }
}