9625번: BABBA

문제 풀이 아이디어

1. 정의
    f(i) = (기계를 i번 눌렀을 때 A의 갯수, 기계를 i번 눌렀을 때 B의 갯수)
2. 구하는 답
    f(K)
3. 초기값
    f(0) = (1, 0)
4. 점화식
    f(i) = (f(i - 1).1, f(i - 1).0 + f(i - 1).1)
			//👉 A의 갯수는 i - 1의 B 갯수
			//👉 B의 갯수는 i - 1의 A의 갯수 + B의 갯수

코드

//BABBA

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

func f(_ n: Int) -> (Int, Int) {
    if n == 0 {
        cache[0] = (1, 0)
    }
    
    if cache[n] == (-1, -1) {
        cache<[n] = (f(n - 1).1, f(n - 1).0 + f(n - 1).1)
    }
    
    return cache[n]
}

let result = f(Int(readLine()!)!)
print(result.0, result.1)