[Swift 알고리즘] 백준 BOJ - 11727 2xn 타일링 2

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

 

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

 

---

Github

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

 

문제 링크

11727번: 2×n 타일링 2

 

---

풀이

이번 문제는 DP를 이용한 문제입니다.

이전 포스팅인 2xn 타일링에서 2x2 타일이 추가된 업그레이드 버전입니다.

 

이번 문제도 어느정도 그려보면 규칙이 보이는 문제인데요.

공책에 하나씩 경우의 수를 그려보면 아래와 같은 규칙이 나오는데요.

1. 이전 구성에 1x2를 더한다. => 이전 구성과 동일한 개수
2. 두 번째 전 구성에 2x2를 더한다. => 두 번째 전 구성의 두 배의 개수

 

이를 식으로 쓰면 아래처럼 나옵니다.

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

 

반복문을 돌리며 위 식대로 값을 구하면 결과를 얻을 수 있습니다.

 

---

전체 코드

//11727 2xn 타일링 2
import Foundation

let input = Int(readLine()!)!

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

---

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

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

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