[프로그래머스] Swift - 아방가르드 타일링

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

 

2024.02.01 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 가로 길이 n, 세로 길이 3인 판을 타일링 해야 한다.
• 2가지 종류의 타일이 존재하며 태일의 개수는 제한이 없다.

타일의 종류

• 각 타일은 90도씩 회전해서 배치가 가능하다
• n이 주어졌을 때 n*3 크기의 판을 타일링 하는 방법의 수를 리턴해야 한다.

 

우선, 한 번에 n에 해당되는 모든 경우의 수를 구할 수 없겠다는 감이 와서 n이 1일 때 부터 단계적으로 타일 배치의 방법의 수를 구해야 될 것 같다고 생각했습니다.

 

따라서, DP를 활용해서 가로 길이를 1씩 증가시켜가며 값을 구해나가야 했습니다.

 

하지만, 점화식을 구하는 거싱 매우 어려웠는데 결과적으로 보면 점화식은 다음과 같습니다.

 

dp[i] = 1*dp[i-1] + 2*dp[i-2] + 5*dp[i-3] + 2*dp[i-4] + 2*d[i-5] + 4*dp[i-6] + 2*dp[i-7] + 2*dp[i-8] + 4*dp[i-9] + 2*dp[i-10] + ....

 

숫자에 색을 칠한 부분을 보면 파란색으로 표시한 처음 3개 (1, 2, 5)를 제외하면 전부 2,2,4 가 반복되는 것을 알 수 있습니다.

이렇게 되는 이유는 n의 크기에 따라 해당 n에서만 만들 수 있는 타일의 개수가 정해져 있기 때문입니다.

 

 

n이 1인 경우에는 당연히 1개의 방법 밖에 없습니다.

n이 2인 경우에는 더이상 분해 할 수 없는 2가지 방법이 새로 생깁니다.

바로 위의 사진과 같은 2개의 방법입니다.

문제에서 보라색 타일로 채운 방법은 n이 1일 때 만들 수 있는 방법을 2개 합친 것이기 때문에 n이 2일 때 새로 추가되는 방법이 아니기 때문제 제외합니다.

 

같은 논리로 n이 3인 경우에는 5가지의 방법이 새로 생깁니다.

이렇게 5가지이다. n이 1인 경우, 2인 경우에서 만들 수 있는 타일링을 조합해서 가로 길이 3을 채우는 경우는 제외합니다.

 

n이 4인 경우에는

a	c	c	c
a	a	b	b
c	c	c	b

 

c	c	c	b
a	a	b	b
a	c	c	c

 

이렇게 2가지 케이스가 새로 생기게 됩니다.

 

더 구해보면

n이 5인 경우에는 2개, 

n이 6인 경우에는 4개,

n이 7인 경우에는 2개,

...

 

이렇게 반복됩니다.

수식으로 나타내면

 

4+3k -> 2개

5+3k -> 2개

6+3k -> 4개

가 됩니다.

 

그래서 점화식이 아래와 같이 되는 것입니다.

dp[i] = 1*dp[i-1] + 2*dp[i-2] + 5*dp[i-3] + 2*dp[i-4] + 2*d[i-5] + 4*dp[i-6] + 2*dp[i-7] + 2*dp[i-8] + 4*dp[i-9] + 2*dp[i-10] + ....

 

이 점화식에 맞게 코드로 구현하면 되는데 보다시피 dp[i]를 구할 때 i-1부터 그 아래까지 쭉 접근해야 해서 시간초과가 발생하는 구조입니다.

 

따라서 반복되는 2,2,4 부분을 별도의 배열에 누적합 형태로 저장해서 시간 복잡도를 낮춰야 합니다.

 

sum이라는 크기 3의 배열을 만듭니다.

sum[j]는 가로 길이를 3으로 나누었을 때 나머지인 j에 해당되는 누적합입니다.

이 sum 배열에 3개씩 반복되는 2,2,4를 곱하는 곱하는 부분들에 대한 합을 계속 더해 나가면서 dp 배열을 갱신합니다.

 

 

풀이

1. solution 함수 구현

fileprivate func solution(_ n:Int) -> Int {
  var dp = Array(repeating: 0, count: 100001)
  var sum = Array(repeating: 0, count: 3)

  dp[0] = 1
  dp[1] = 1
  dp[2] = 3
  dp[3] = 10

  let mod = 1_000_000_007
  
  if n <= 3 {
    return dp[n]
  }
  
  for i in 4...n {
    dp[i] += dp[i-1] + dp[i-2]*2 + dp[i-3]*5
    sum[(i-4)%3] = (sum[(i-4)%3] + dp[i-4]) % mod
    dp[i] += (sum[0] + sum[1] + sum[2] + sum[i%3])*2 // sum[i%3]을 더해주는 이유는 2,2,4의 반복에서 4의 차례일 때가 i%3 번째이기 때문에 한번 더 더해줘서 4를 만들어주는 것이다.
    dp[i] %= mod
  }
  
  return dp[n]
}

 

문제에서 주어진 대로 dp[0] ~ d[3] 까지는 값을 채워 넣고 4부터 반복문을 통해 점화식을 사용하여 채워나갑니다.

 

sum[(i-4)%3] 에서 i에 4를 빼고 3을 나눈 다음 갱신하는 이유는 

예를 들어 dp[7]의 경우 2, 2, 4 반복에서 가장 처음 2에 해당된다. 따라서 0번째 위치에 갱신시켜야 하기 때문에 (7-4)%3 을 수행해서 올바른 인덱스로 조정한 것입니다.

 

dp[i] += (sum[0] + sum[1] + sum[2] + sum[i%3])*2 

에서 sum[i%3] 을 더해주는 이유는 2,2,4 반복에서 4에 위치하는 것이 i%3이기 때문입니다.

다른 위치와 다르게 2가 아닌 4개의 케이스가 추가되기 때문에 한 번 더 더해줘서 2,2,4 반복을 맞춰줍니다.

 

 

 

마무리

Level 3치고는 매우 어려웠던 것 같습니다.

직접 n이 4부터 7정도까지는 그려봐야 규칙을 찾을 수 있는데 이 규칙을 찾고 난 다음에도 점화식을 세우고 이 점화식을 코드로 어떻게 구현할지에 대한 어려움이 연속해서 생겼습니다.

 

저도 명확한 해결책을 찾지 못해서 다른 분들이 올려준 힌트와 정답 코드를 보고 많이 참고해서 푼 문제였습니다.