[프로그래머스] 멀리뛰기 # DP

문제 링크

1. 문제

 전체 칸 수 n이 주어질 때 1칸 또는 2칸을 이동해 n칸을 이동하는 경우의 수에 1234567을 나눈 나머지를 반환하는 함수를 완성하라. 

2.  제한 사항

1 <= n <= 2000

 

3. 입출력 예

 

---

 

4. 첫 번째 풀이 - Python

 결국 초기값만 다른 피보나치 수열이다. n이 2000 이하이므로 메모이제이션을 사용하지 않았다. 메모이제이션을 사용했을 때는 0.18ms, 사용하지 않았을 때는 최대 0.15ms가 소요되었다. 

 

def solution(n):
    MOD = 1234567
    if n == 1:
        return 1
    if n == 2:
        return 2
        
    a, b = 1, 2
    for i in range(3, n + 1):
        a, b = b, (a + b) % MOD
    
    return b

 

 

5. 두 번째 풀이 - Java 

import java.util.*;

class Solution {
    public long solution(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        int a = 1, b = 2;
        int MOD = 1234567;
        
        for (int i = 3; i <= n; i ++) {
            int temp = (a + b) % MOD;
            a = b;
            b = temp;
        }
        return b;
    }
}

 

 

6. 느낀점

 결국 피보나치 수열과 동일한 형태라는 것을 캐치하는 시간이 좀 걸렸다. 1칸과 2칸을 사용하는 모든 경우의 수를 어떻게 세어야 하는지 고민했었는데 n이 1일 때부터 5일 때까지 쭉 써보니 결국 피보나치 수열과 같이 F(n) = F(n-1) + F(n-2) 가 반복되는 패턴을 발견했다. 항상 느끼는 것이지만 문제의 원리를 발견하는 것이 제일 중요한 것 같다.