티스토리 뷰
2133번: 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
www.acmicpc.net
타일 채우기
문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
입력
첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.
출력
첫째 줄에 경우의 수를 출력한다.
예제 입력 1
2
예제 출력 1
3
풀이
타일링 문제는 이전에 풀었던 경험이 있다.
바로 이 문제이다.
1793번: 타일링
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다.
www.acmicpc.net
위의 타일링 문제에서 좀 더 진화된 문제가 이번 문제로,
3*n 크기를 2*1, 1*2 크기의 타일로 채워야 한다.
3*n이니 2*n 문제를 풀때보다 예외를 좀 더 생각하며 문제를 풀어야 한다.
설계
n의 홀수, 짝수 판단
2*n 크기의 문제는 n이 홀수이든, 짝수이든 상관이 없었다. 2*1, 1*2 크기의 타일로 모든 벽을 채울 수 있었기 때문이다.
하지만, 3*n 문제는 n이 짝수일 때만 2*1, 1*2 크기의 타일로 벽을 채울 수 있다.
n일 홀수라면 1*1 크기의 공간이 항상 남기 때문이다.
일단 n이 짝수일 때만 타일 채우기가 가능하다는 건 알았다.
어떻게 타일을 채울 것인가?
일단 n이 2일때부터 경우의 수를 확인해보자.
1️⃣ n=2
3*2의 크기를 채우는 경우의 수는 모두 3가지이다.
dp[2] = 3
2️⃣ n=3
홀수니까 X
3️⃣ n=4
3*4의 크기를 채우는 경우의 수는 모두 11가지이다.
주황색으로 색칠한 오른쪽을 보면 n=2일때의 3개의 경우의 수가 나오는 것을 확인할 수 있다.
총 n=2일때의 경우의 수가 3번씩 나오므로 dp[4] = dp[2]*3 이라고 할 수 있다.
또 예외인 경우가 2가지이니, dp[4] = dp[2]*3 + 2 를 해준다.
4️⃣ n=6
n=4일때부터 예외인 경우는 타일이 계속 붙으면서 점점 증가하게 된다.
그래서 n=6일때는 (예외를 제외한 경우의 수 + n=4일때 옆에 붙을 dp[2]의 경우의 수 + n=6일때 예외 경우의 수)를 계산해줘야 한다.
dp[6] = dp[4] * 3 + dp[2]*2 + 2
구현
설계한 방법대로 코드를 구현해보자.
처음 내가 만들었던 코드인데, 왜인지 모르겠는데 백준에서 계속 런타임에러가 났다........
난 어차피 짝수만 계산하면 되니 dp[0] => n=2인 경우의 수, dp[1] => n=4인 경우의 수 이런식으로 dp배열의 크기를 반으로 줄여서 하려고 했다. 하지만 런타임에러,,,,,
let N = Int(readLine()!)!
var dp = [Int](repeating: 0, count: max(N/2+1, 2))
dp[0] = 3
dp[1] = 11
var tmp = 0
if N>2 {
for i in 2..<N/2{
tmp+=dp[i-2]*2
dp[i] = dp[i-1]*3+2 + tmp
}
}
print(N%2==0 ? dp[N/2 - 1] : 0)
그래서 코드를 좀 수정해서 다시 시도했더니 통과했다... 배열의 크기 때문인가?
전체코드
let n = Int(String(readLine()!))!
var dp = Array(repeating: 0 ,count: 31)
dp[0] = 1
dp[2] = 3
for i in stride(from: 4, through: n, by: 1){
dp[i] = dp[i - 2] * 3
for j in stride(from: 4, through: i, by: 2){
dp[i] += dp[i - j] * 2
}
}
print(dp[n])
'백준 > 백준 - 스위프트' 카테고리의 다른 글
1991번: 트리 순회 (0) | 2023.10.12 |
---|---|
11725번: 트리의 부모 찾기 (0) | 2023.10.11 |
12933번: 오리 (0) | 2023.09.30 |
3085번: 사탕 게임 (0) | 2023.09.25 |
21317번: 징검다리 건너기 (0) | 2023.09.13 |