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

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 2193 이친수" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

2193번: 이친수

 

---

풀이

이번 문제는 DP를 이용한 문제입니다.

 

개수의 규칙을 이용한 풀이와 이친수 규칙을 이용한 풀이로 나눠 풀어봤는데요.

 

해당 문제는 1, 1, 2, 3, 5...로 피보나치 수와 동일합니다.

즉, dp[i] = dp[i-1] + dp[i-2]로 해결할 수 있습니다.

 

두 번째 풀이는 이친수의 규칙입니다.  n이 3 이상인 경우 뒤에 0과 1을 붙일 수 있는 규칙도 존재하는데요.

0은 앞에 무엇이 오든 상관 없이 붙일 수 있습니다. 즉 i 번째 0으로 끝나는 이친수는 이전 0으로 끝나는 경우의 수와 1로 끝나는 경우의 수의 합입니다.

1로 끝날 수 있는 경우는 앞에 0이 올 때만 가능합니다. 즉, i 번째 1로 끝나는 이친수의 개수는 이전 0으로 끝나는 경우의 수와 같습니다.

이를 코드로 표현하면 아래와 같습니다.

let temp = dp[0]
dp[0] = dp[0] + dp[1]
dp[1] = temp

 

저는 두 번째 풀이가 문제에 더 어울린다고 생각합니다.

여러분도 두 가지 방법 모두로 해결을 해보세요.

 

---

전체 코드

//2193 이친수
import Foundation

let input = Int(readLine()!)!

var dp: [Int] = [0, 1]
if input >= 2 {
    for _ in 2...input {
        let temp = dp[0]
        dp[0] = dp[0] + dp[1]
        dp[1] = temp
    }
}

print(dp[0] + dp[1])

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.