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

//dfs으로 하면 시간초과
// % 1234567이니까 무조건이다.
/*
1
1

2
11
2

3
111
21
12

4
1111
112
121
211
22

5
11111
1112
1121
1211
2111
221
122
212

6
111111
11112
11121
11211
12111
21111
2211
2112
2121
1122
222

dp[n] = dp[n-1] + dp[n-2]


*/

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

 

풀이

1. 우선 % 1234567을 한다는건 경우의수가 엄청나다는 것이니 탐색으로는 풀 수 없다.

2. 하나씩 규칙을 확인해봤다. 처음에는 1 + (n/2 ~ n-1의합) + n%2==0일경우 +1 이런식으로 풀었는데 틀렸다.

3. 다시보니 dpn은 (dp-1) + (dp-2)였다. 그렇게 dp로 문제를 해결했다.

 

느낀점

- 우선 뭔가 점화식이 듣도보도 못한 이상한 느낌이 든다면 웬만하면 틀린거였다...

- 웬만한 점화식은 깔끔하고 아름답게 생겼다. 이렇게 생각해야 빠르게 해답을 찾는 것 같다.

 

 

 

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

프로그래머스