프로그래머스 lv2 멀리 뛰기

문제 링크

멀리 뛰기

풀이

• 또 재귀로 풀었다가 시간초과 났다. 처음에는 재귀를 이용한 dfs로 생각했기 때문.
• dp로 푸는 습관을 들여야겠다.
• 결론적으로는 피보나치와 동일하다.
  • 처음에 1칸으로 뛰는건 한 가지 경우의 수, 그리고 2번째 칸으로 뛰는건 1-1, 2 으로 2칸이다.
  • 이제 n을 향해 뛰는 것은 다음과 같이 생각해 볼 수 있다.
    • [n - 1] 번째 칸에서 1칸을 뛰어 n 으로 도착
    • [n - 2] 번째 칸에서 2칸을 뛰어서 n 으로 도착
  • 첫 번째 방법은 마지막에 1칸만 더 뛰어서 도착하고, 2번째 방법은 마지막에서 2칸을 뛰어서 도착한 것이기에 두 가지 방법중에 중복되는 것은 없다.
    • 예시를 들어보자
      • 2번 칸으로 점프하는 경우
        • 1 - 1
        • 2
      • 3번 칸으로 점프하는 경우
        • 1 - 1 - 1
        • 1 - 2
        • 2 - 1
      • 4번 칸으로 점프하는 경우
        • (n-2) 에서 점프하는 경우
          • 1 - 1 - 2
          • 2 - 2
        • (n-1) 에서 점프하는 경우
          • 1 - 1 - 1 - 1
          • 1 - 2 - 1
          • 2 - 1 - 1
  • 그래서 결론은 피보나치를 구하는 문제가 되어버린다.
  • 거기에 모듈러 연산 한 스푼 얹어주면 문제를 풀 수 있다.

class Solution {
    public long solution(int n) {
        long[] memory = new long[2001];

        memory[0] = 0;
        memory[1] = 1;
        memory[2] = 2;

        // f[n] = f[n-1] + f[n-2]?
        for (int i = 3; i <= n; i++) {
            memory[i] = (memory[i - 1] + memory[i - 2]) % 1234567;
        }

        return memory[n];
    }
}