11726번: 2×n 타일링

문제 풀이 아이디어

2xn의 직사각형을 만드는 방법은

1. 2x(n - 1)의 직사각형에 1 x 2 타일을 하나 붙이는 방법과
2. 2x(n - 2)의 직사각형에 2 x 1 타일 2개로 정사각형을 만들어 붙이는 방법이 있습니다.

따라서 점화식은 f(n) = f(n - 2) + f(n - 1)로 피보나치 수열과 동일합니다.

코드

재귀함수를 이용한 방법

// 2 * n 타일링
let n = Int(readLine()!)!

var cache = Array(repeating: -1, count: n + 1)

// 재귀함수를 이용해서 구현하기
func f(_ n: Int) -> Int {
    // cache에 초기값 넣어주기
    if n == 1 || n == 2 {
        cache[n] = n
    }
    
    // 저장된 값이 없다면 점화식으로 계산한다.
    if cache[n] < 0 {
        cache[n] = (f(n - 2) + f(n - 1)) % 10007
        //❗️ Int 범위 벗어나는 것을 방지하기 위해 나누는 수는 미리 나누어서 cache에 저장
    }
    //👉 이렇게 하면 재귀함수가 f(1)까지 내려가서 역으로 f(n)까지 구하면서 올라옴
    
    return cache[n]
}

print(f(n))

반복문을 이용한 방법

// 2 * n 타일링
let n = Int(readLine()!)!

var cache = Array(repeating: -1, count: n + 1)

for i in 1...n {
    // 초기 값 넣기
    if i == 1 || i == 2 {
        cache[i] = i
        continue
    }
    
    // 점화식 적용
    cache[i] = (cache[i - 2] + cache[i - 1]) % 10007
}

print(cache[n])