멀리 뛰기

작성일: 2024-11-03

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

접근 방식

dfs가 바로 생각나서 풀어봤는데, 역시나 시간초과가 발생했다.

그래서 메모리를 통한 방식을 생각해보게 되었는데, 특정 패턴이 발견되었다.

1칸을 뛸 수 있는 방식은 [1] 한 가지다.
2칸을 뛸 수 있는 방식은 [1, 1] [2] 두 가지다.
3칸을 뛸 수 있는 방식은 [1, 1, 1] [2, 1] [1, 2] 세 가지다.
4칸을 뛸 수 있는 방식은 [1, 1, 1, 1] [2, 1, 1] [1, 2, 1] [2, 1, 1] [2, 2] 네 가지다.

여기서 뭔가 패턴이 보이는 것 같다. 이어서 더 알아보자.

5칸은 [1, 1, 1, 1, 1] [1, 2, 2] [2, 1, 2] [2, 2, 1] [2, 1, 1, 1] [1, 2, 1, 1] [1, 1, 2, 1] [1, 1, 1, 2] 8가지다.

현재 방식에서 뛸 수 있는 방식은 전과 전전 방식의 합과 같다.

이는 mod 연산에도 동일하게 적용된다. 따라서, 1과 2를 사전에 연산을 해 두고, n만큼 for문을 돌린다면 쉽게 정답을 알 수 있다.

결과

소스 코드

class Solution {
    static long answer = 0;
    public long solution(int n) {
        int arr[] = new int[2001];

        arr[1] = 1 % 1234567;
        arr[2] = 2 % 1234567;
        for(int i=3; i<=n; i++){
            arr[i] = (arr[i-1] + arr[i-2])%1234567;
        }
        return arr[n];
    }

}

다른 접근 방식

없음.

알게 된 점

없음.