멀리 뛰기

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12914

문제설명

• 주어진 파라미터: int n
• 반환값: long
• 효진이 멀리뛰기 1,2칸 뛸 수 있음
• 멀리뛰기에 사용될 칸의 수 n → 끝에 도달하는 방법의 가지수 알아내기
• 가지수를 1234567로 나눈 나머지 return

풀이방식

1. 뛸 수 있는 칸 → 1 or 2 → 갈 수 있는 방법 1 2 뿐

2. 이전까지의 합과 본인을 더했을때 n이 나오면 방법 + 1, n 보다 커지면 방법이 되지 못함

3. (풀이1) 재귀로 풀 수 있을 듯 → 시간초과

4. (풀이2) 규칙성 찾기

   • 1 → 1
   • 2 → 2
   • 3 → 3
   • 4 → 5
   • 5 → 8
   • 6 → 13

   ⇒ 피보나치처럼 -1, -2 값을 더하면 본인 값이 나오는 것을 알 수 있다.

코드

(풀이 1)

class Solution {
    
    static int N = 0;
    static int ANSWER = 0;

    
    public long solution(int n) {
        N = n;
        recur(0);
        return ANSWER%1234567;
    }
    
    public void recur(int num){
        // 종료조건
        if(N == num){
            ANSWER++;
            return;
        }else if( num > N){
            return;
        }
        
        // 반복조건
        recur(num+ 1);
        recur(num+ 2); 
    }
}

⇒ 시간초과 실패

(풀이 2)

import java.util.*;

class Solution {
    
    static Map<Integer, Integer> m = new HashMap<>();
    
    public int solution(int n) {
        return calc(n);
    }
    
    public int calc(int num) {
        if (num == 1) return 1; 
        if (num == 2) return 2; 

        if (!m.containsKey(num)) {
            m.put(num, (calc(num - 1) + calc(num - 2)) % 1234567); 
        }
        
        return m.get(num);
    }
}

⇒ % 1234567 하는 부분에서 오버플로우가 발생해 계산에 오차가 나는 것을 확인

⇒ 대입할때부터 나머지 계산을 진행해 큰수로 넘어가는 것을 방지함으로써 해결

회고

다른사람의 풀이를 보다 재미있는 풀이가 보여 소개합니다.

class Solution {
    long[] dp = new long[2001];
    public long solution(int n) {
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < dp.length; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
        }
        return dp[n];
  }
}

피보나치 수열을 배열로 해석했다는 부분이 흥미롭습니다.

한가지 문제에도 재귀, 피보나치(배열, 재귀-Map 활용) 3가지 혹은 그 이상의 해결법이 존재한다는게 너무 재밌었고, 스스로도 이런 다양한 해결법을 생각할 수 있도록 성장해보겠습니다.😉

---

참 쉬워질때까지..