[Swift 알고리즘] Programmers 멀리뛰기

×

Level 2 연습문제

멀리뛰기

정답률 64%라서 만만하게 봤는데, 함정? 이 꽤 있는 문제였다. 

<Check Point>

피보나치수열 / 점화식 / 정수 오버플로우 / 재귀말고 dp 

문제 설명
멀리 뛰기를 연습하고 있습니다. 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 다음의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다.
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
멀리뛰기에 사용될 칸의 수 n이 주어질 때, 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한 사항
- n은 1 이상, 2000 이하인 정수입니다.

입출력 예시

print(solution(4)) //5
print(solution(3)) //3

1차시도 37.5점 시간초과

재귀로 구현해봤는데 역시나 시간초과로 실패. 같은 재귀라도 더 효율적으로 구할 수 있는데, 좋은 방법은 아닌것 같다. 

func solution(_ n:Int) -> Int {
    var result = 0

    func dfs(_ i:Int) {
        if i > n { return }
        else if i == n {
            result += 1
            return
        }
        dfs(i + 1)
        dfs(i + 2)
    }
    dfs(1)
    dfs(2)

    return result % 1234567
}

 

2차시도 37.5점 illegal instruction (core dumped)?

테스트 케이스를 직접 손으로 더 해보니까 피보나치 수열이더라!

이걸 직접 손으로 다 해보지 않고도 피보나치 수열인 걸 알아챌 수 있을까...

아무튼 다음과 같이 구현이 잘 된 것 같은데 왜?? 실패가 뜨지?

func solution(_ n:Int) -> Int {
    var first = 0
    var second = 1
    for i in 0..<n {
        let temp = first + second
        first = second
        second = temp 
    }
    return second % 1234567
}

이건 내 능력 밖인 것 같아서 검색을 해보니, 정수 오버플로우 때문이라고 한다. 

 

통과 답안

func solution(_ n:Int) -> Int {
    var first = 0
    var second = 1
    for i in 0..<n {
        let temp = first + second
        first = second
        second = temp % 1234567
    }
    return second
}

수열을 계속해서 만들어나가면 Swift의 Int 범위를 넘어서는 수가 발생할 수 있기 때문에, 런타임 오류가 발생. 

따라서 수열을 저장하는 것이 아니라, 1234567로 나눈 나머지의 결과값을 저장해야. 

 

+ 동적계확법으로 푸는 방법

딱히 더 효율적이진 않아보이지만 그냥 참고용으로.. 재귀보다는 낫다.. 

func solution(_ n:Int) -> Int {
    var dp = Array(repeating: 0, count: n+1)
    
    if n < 3 { return n }
    
    dp[1] = 1
    dp[2] = 2
    
    for i in 3...n {
        dp[i] = (dp[i-2] + dp[i-1]) % 1234567
    }

    return dp[n]
}