일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- swift 연속된 부분 수열의 합
- swift 2xn 타일링 풀이
- swift ac 문제풀이
- 백준 2xn 타일링
- swift dfs
- swift
- ac swift 풀이
- MVVM
- swift 연속된 부분 수열의 합 풀이
- 연속된 부분 수열의 합 swift
- ios
- 연속된 부분 수열의 합 투포인터
- rxswift
- swift 2xn 타일링
- swift 백준 9095
- 백준 2xn 타일링 풀이
- swift 2xn 타일링 백준
- swift 9095 풀이
- iOS Charts
- swift algorithm
- swift ac 풀이
- swift 프로그래머스
- swift gRPC
- ac 투포인터
- swift ac
- 123 더하기 풀이
- ac 구현 풀이
- swift 알고리즘
- swift codility
- 1 2 3 더하기 풀이
- Today
- Total
boraBong
[Swift] 11726번: 2xn 타일링 문제 풀이 [BOJ - Silver3] 본문
💬 문제
https://www.acmicpc.net/problem/11726
💬 Idea
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하자.
주어지는 직사각형의 너비 길이가 길어짐에 따라 이를 2x1, 1x2의 작은 단위 조합으로 쪼개어 본다면 규칙을 찾을 수 있었다.
기본적으로
2x1 크기의 직사각형은 2x1 타일 1개로만 채워질 수 있기에 1가지의 방법을 갖고
2x2 크기의 직사각형은 2x1 타일 2개 또는 1x2 타일 2개로 채워질 수 있기에 2가지의 방법을 갖는다.
💡 다음으로 2x3 크기의 직사각형을 채우는 방법의 수를 알아보자.
2x3 크기의 직사각형을 2x1 과 1x2를 기준으로 쪼개어 본다면 아래 두 개의 조합이 나온다.
- 2x1 타일 1개 + 2x2 타일 1개
- 우리는 이전 단계에서 2x2 타일을 채우는 방법의 수를 구해놓았으므로 2가지임을 알 수 있다.
- 따라서 2x1 타일 1개와 2x2 타일 1개 조합으로 채울 수 있는 방법은 2가지 이다.
- 1x2 타일 2개 + 2x1 타일 1개
- 2x1 타일을 채우는 방법의 수는 1가지이다.
위 두 개의 조합의 가지수를 더하면 2x3 크기의 직사각형을 채울 수 있는 방법의 수를 도출할 수 있으므로
2x3 크기의 직사각형을 채울 수 있는 방법의 수는 3개이다. (2 + 1 = 3)
💡다음으로 2x4 크기의 직사각형을 채우는 방법의 수를 알아보자.
2x4 크기의 직사각형을 2x1 과 1x2를 기준으로 쪼개어 본다면 아래 두 개의 조합이 나온다.
- 2x1 타일 1개 + 2x3 타일 1개
- 2x3 타일을 채우는 방법의 수를 우리는 이전 단계에서 구해놓았으므로 3가지임을 알 수 있다.
- 따라서 2x1 타일 1개 + 2x3 타일 1개 조합으로 채울 수 있는 방법은 3가지 이다.
- 1x2 타일 2개 + 2x2 타일 1개
- 2x2 타일을 채우는 방법의 수를 우리는 이전 단계에서 구해놓았으므로 2가지임을 알 수 있다.
- 따라서 2x1 타일 1개 + 2x2 타일 1개 조합으로 채울 수 있는 방법은 2가지 이다.
위 두 개의 조합의 가지수를 더하여 2x4 크기의 직사각형을 채울 수 있는 방법의 수를 도출할 수 있으므로
2x4 크기의 직사각형을 채울 수 있는 방법의 수는 5개이다. (3 + 2 = 5)
이렇게 직사각형을 쪼개어 생각해볼 수 있고 단계를 반복할 수록 아래와 같은 규칙을 따른다.
즉 2xn의 직사각형 을 1x2, 2x1의 타일로 채울 수 있는 방법의 수를 알기 위해서는
→ 이전 두개의 항 각각의 방법의 개수를 알고 있다면 해결할 수 있게 된다.
이를 점화식으로 표현해본다면 아래와 같다.
💬 풀이
import Foundation
func solution11726() {
let N = Int(readLine()!)!
var rectangleArr = Array(repeating: 0, count: N + 1)
if N == 1 {
print(1)
} else if N == 2 {
print(2)
} else {
rectangleArr[1] = 1
rectangleArr[2] = 2
for i in 3...N {
rectangleArr[i] = (rectangleArr[i - 1] + rectangleArr[i - 2]) % 10007
}
print(rectangleArr[N])
}
}
'iOS > Algorithm' 카테고리의 다른 글
[Swift] 5430번: AC 문제 풀이 [BOJ - Gold5] (0) | 2023.04.21 |
---|---|
[Swift] 연속된 부분 수열의 합 문제 풀이 [Programmers - Level2] (0) | 2023.04.18 |
[Swift] 9095번: 1, 2, 3 더하기 문제 풀이 [BOJ - Silver3] (2) | 2023.04.06 |
[Swift] 삼각 달팽이 문제 풀이 [Programmers - Level2] (2) | 2023.04.05 |
[Swift] 조이스틱 문제 풀이 [Programmers - Level2] (4) | 2023.04.04 |