[Swift 알고리즘] 백준 BOJ - 11726 2×n 타일링

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 11726 2×n 타일링" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

11726번: 2×n 타일링

 

---

풀이

이번 문제는 DP 문제입니다.

DP는 케이스를 하나하나 적어보며 규칙을 찾는 것도 좋은 풀이 방법입니다.

공책에 채우는 방법을 하나하나 그려보면서 글을 읽어보세요.

 

2x1 : 2x1 타일 1개로 채우는 방법 1가지

2x2 : 2x1 타일 2개, 1x2 타일 2개로 채우는 방법 2가지

 

2x3을 채우는 방법은 위 그림과 같습니다.

빨간색 표시가 없는 부분을 잘 보시면 2x2를 채운 구성과 2x1을 채운 구성이라는 것을 알 수 있습니다.

이들의 구성에 빨간색 표시를 추가한 것 뿐입니다.

 

직전 구성에 1x2를 추가하고, 두 번째 전 구성에 2x1 두 개 블록을 추가합니다.

2x4, 2x5도 그려보시면 동일하다는 것을 알 수 있을 겁니다.

 

이를 식으로 표현하면 아래 식처럼 나옵니다.

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

 

즉, 이번 문제의 결과값은 i-1번째 값 + i-2번째 값입니다.

 

---

전체 코드

//11726 2×n 타일링
import Foundation

let input = Int(readLine()!)!

var dp: [Int] = [0, 1, 2]
if input >= 3 {
    for i in 3...input {
        dp.append((dp[i-1] + dp[i-2]) % 10007)
    }
}
print(dp[input])

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.