반응형
안녕하세요. 개발 중인 정주입니다.
오늘은 "백준 BOJ - 11727 2xn 타일링 2" 문제를 풀었습니다.
Github
GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘
스위프트 알고리즘. Contribute to jeongju9216/SwiftAlgorithm development by creating an account on GitHub.
github.com
문제 링크
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
풀이
이번 문제는 DP를 이용한 문제입니다.
이전 포스팅인 2xn 타일링에서 2x2 타일이 추가된 업그레이드 버전입니다.
이번 문제도 어느정도 그려보면 규칙이 보이는 문제인데요.
공책에 하나씩 경우의 수를 그려보면 아래와 같은 규칙이 나오는데요.
- 이전 구성에 1x2를 더한다. => 이전 구성과 동일한 개수
- 두 번째 전 구성에 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])
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.
반응형