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정도까지는 그려봐야 규칙을 찾을 수 있는데 이 규칙을 찾고 난 다음에도 점화식을 세우고 이 점화식을 코드로 어떻게 구현할지에 대한 어려움이 연속해서 생겼습니다.
저도 명확한 해결책을 찾지 못해서 다른 분들이 올려준 힌트와 정답 코드를 보고 많이 참고해서 푼 문제였습니다.
'알고리즘' 카테고리의 다른 글
[프로그래머스] Swift - 에어컨 (1) | 2024.02.05 |
---|---|
[프로그래머스] Swift - n + 1 카드게임 (1) | 2024.01.31 |
[프로그래머스] Swift - 주사위 고르기 (0) | 2024.01.22 |
[프로그래머스] Swift - 고고학 최고의 발견 (0) | 2024.01.19 |
[프로그래머스] Swift - 산 모양 타일링 (0) | 2024.01.18 |
댓글