[프로그래머스] 산 모양 타일링 - 2024 카카오 겨울 인턴십

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

2024 KAKAO WINTER INTERNSHIP 문제였던 다이나믹 프로그래밍 문제입니다. 실전에서는 해결하지 못하였으나 프로그래머스에 올라와 있길래 다시 도전하였습니다.

---

산 모양 타일링

정삼각형을 2n + 1개 이어 붙여 밑변의 길이가 n + 1, 윗변의 길이가 n인 사다리꼴을 만듭니다. 윗변과 변을 공유하는 n개의 삼각형 각각은 머리(top)가 붙어 있을 수도 있고, 없을 수도 있습니다. 머리가 있는지 없는지 여부는 tops 배열을 통해 주어집니다.

산 없는 산 모양 타일링

우선 tops의 값이 전부 0이라고 생각하고, 2n + 1개의 삼각형으로 이루어진 사다리꼴을 채우는 경우의 수를 구해 봅시다. 이 부분만 놓고 본다면 주어진 n에 대하여 2n + 1 크기의 타일을 1칸 또는 2칸짜리 타일로 채우는 경우의 수를 구하는 문제가 됩니다.

점화식을 천천히 생각해 봅시다. 매 순간 내릴 수 있는 결정은 2가지입니다.

• 1칸짜리 삼각형 배치
• 2칸짜리 마름모 배치

여기서, 마름모를 놓을 때 주의하여야 합니다.

만약 1번 위치에 마름모를 사용한다고 하면 아래와 같이 생각할 수 있습니다.

하지만 지금은 아래와 같이 생각해야 해야 합니다.

i번째 인덱스에 대한 연산을 마쳤을 때, i번째 값은 i가 끝이라는 가정 하에 계산된 경우의 수를 가지고 있어야 합니다. 만약 i번째 칸에 해당하는 답을 구하는 단계에 i+1번 칸을 고려해야 한다면... 휴! 지금은 만약으로라도 고려하지 않겠습니다.

말이 두서가 없지만 말하고자 하는 바를 i번째 칸까지 채우는 경우의 수에 대한 점화식으로 나타내면 다음과 같습니다.

dp[i] = dp[i-1] + dp[i-2]

// 나머지 연산 적용
const MOD = 10_007;
dp[i] = (dp[i-1] + dp[i-2]) % MOD;

1. i-1까지 채운 상태에서 1칸짜리 삼각형 배치
2. i-2*까지 채운 상태에서 2칸짜리 마름모 배치

두 가지 경우가 있으므로 i-1까지 채우는 경우의 수와 i-2까지 채우는 경우의 수를 더하여 i까지 채우는 경우의 수를 구할 수 있습니다. 정확히는 아래와 같이 나타낼 수 있습니다.

(i까지 채우는 경우의 수) = (i-1까지 채우는 경우의 수) * (i를 채우는 경우의 수) + (i-2까지 채우는 경우의 수) * (i-1, i를 동시에 채우는 경우의 수)

i를 채우는 경우의 수와 i-1, i를 마름모로 동시에 채우는 경우의 수가 둘 다 1이므로 생략 가능합니다.

점화식을 반복하기 위해 초기에는 적당히 0번 인덱스에 삼각형 하나를 놓을 수 있는 경우의 수인 1을 할당하고 1번 인덱스에는 두 개의 삼각형 또는 하나의 마름모를 놓을 수 있으므로 2를 할당합니다.

const dp = new Array(2*n + 1).fill(0);

dp[0] = 1;
dp[1] = 2;

2 이상의 나머지 인덱스에 대하여 점화식을 반복하면 tops가 전부 0인 경우의 답을 얻을 수 있습니다.

여기까지의 코드

const MOD = 10_007;
const dp = new Array(2 * n + 1).fill(0);
dp[0] = 1;
dp[1] = 2;

for (let i = 2; i < n * 2 + 1; i++){
    dp[i] = (dp[i-1] + dp[i-2]) % MOD;
}

dp[2*n];

 

산 있는 산 모양 타일링

거의 다 왔습니다. 이제 tops를 고려하도록 식을 수정해 봅시다.

사다리꼴 중간중간에 뾰족한 머리가 생겼을 때, 무엇이 달라지는가 하면...

 

다시 1번 인덱스를 기준으로 생각해 봅시다.

원래는 i-1까지 채워진 경우, 삼각형 하나로 i번째 칸을 채우는 한 가지 방법밖에 없었습니다.

하지만, 위에 한 칸이 더 생긴다고 한다면 다음과 같이 두 가지 경우로 늘어나게 됩니다.

 

1. 두 개의 삼각형 배치
2. 마름모 배치

이와 같은 차이를 반영하려면 일단 tops가 적용되는 인덱스를 찾아야 합니다. tops는 짝수 번째 삼각형에 붙을 수 있으며, 인덱스를 기준으로는 1, 3, 5 등 홀수 인덱스에 해당합니다.

1, 3, 5와 같은 2*n + 1의 숫자들로 tops를 인덱싱하기 위해 0, 1, 2로 변환하여야 하므로 이들 인덱스를 2로 나눈 몫을 취하여 tops 배열에 접근할 수 있도록 합니다.

타일 인덱스	1	3	5
tops 인덱스	0	1	2

타일 인덱스가 홀수이면서 타일 인덱스를 변환하여 tops에 접근한 결과(top)가 1인 경우에는 위와 같이 확장된 경우의 수를 반영하고, top이 0인 경우에는 기존의 점화식을 그대로 사용합니다.

top이 1인 경우의 점화식은 다음과 같습니다.

dp[i] = dp[i-1] * 2 + dp[i-2]

 

한 가지 주의할 점. 아까는 top을 고려하지 않고 dp[1]의 값을 2로 할당하였습니다. 지금은 tops[0]의 값이 1인 경우, 실제 경우의 수는 3이 되므로 이 부분도 수정합니다.

완성 코드

const MOD = 10_007;
const dp = new Array(2 * n + 1).fill(0);
dp[0] = 1;
dp[1] = tops[0] ? 3 : 2;

for (let i = 2; i < n * 2 + 1; i++){
    // 1과 비교하는 부분 전부 생략 가능
    if (i % 2 === 1 && tops[Math.floor(i/2)] === 1){ 
        dp[i] = (dp[i-1] * 2 + dp[i-2]) % MOD; 
    } else {
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    }
}
dp[2*n];

---

팁

나머지 연산

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction

나머지 연산은 매 단계에 적용하여 dp 테이블에 기록된 값이 10007 미만으로 유지될 수 있도록 합니다.

---

공식 문제해설

2024 카카오 겨울 인턴십 코딩테스트 문제해설