[Swift 알고리즘] 백준 2193 이친수

안녕하세요 코코종입니다.

오늘을 마지막으로 저는... 프로그래머스로 떠납니다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그래서 조금 간단한 문제를 들고 왔답니다

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/30.
//

import Foundation
// 백준 2193 이친수 dp 실3

// 이친수는 0으로 시작하지 않는다.
// 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

// dp로 기획해서 앞에꺼에 뒤가 0이라면 2 더하고 1이라면 1더함

// dp[i] = dp[i-1] + dp[i-2]
// 1 // 0 - 0, 1 - 1
// 10 // 0 -1, 1 - 0
// 100 101 // 1,1
// 1000 1001, 1010 // 2,1
// 10000 10001, 10010, 10100 10101 // 3, 2
// 100000 100001, 100010, 100100 100101, 101000 101001, 101010 // 5, 3
let n = Int(readLine()!)!
var dp: [Int] = []

dp.append(0)
dp.append(1)
if n >= 2 {
    for i in 2...n {
        let v = dp[i-1] + dp[i-2] // 피보나치
        dp.append(v)
    }
}
print(dp[n])

어려운 부분은 없었고 하나씩 구하다보니 답이 보였답니다(피보나취)

다른분들의 해설을 참고하다보니 결국 이천수는 10으로 시작할 수 밖에 없고 그 뒤에는 들어갈 수 있는 경우를 찾는 것이어따.

주석으로 표기한 부분을 보면 0으로 끝나는 갯수과 1로 끝나는 갯수를 따로 계산했는데요.

결국 i번째의 0의 갯수와 1의 갯수는 i-1과 i-2의 0의 갯수, 1의 갯수과 같다고 알게 되었답니다.

그리고 놓쳤던 부분이 있다면 n의 범위가 1~90이었기 때문에 1일때는 2..n 으로 하면 인덱스 오류가 발생해서 99퍼에서 런타임 오류가 났답니다 ㅎ... 참고하세요!

 

다음주부터는 프로그래머스로 돌아오겠습니다!