[프로그래머스] lv2 멀리 뛰기 (JAVA)

1. 문제

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

프로그래머스

 

---

 

2. 문제 풀이 겸 회고

처음에는 단지 N <=2000이라고 했는데, dfs 해서 백트레킹만 잘하면 되겠지라는 생각을 하고 DFS로 구현했다..

1 1 1 1 → 1 1 2  → 1 2 1  → 2 1 1  → 2 2

if(sum==n){ // 기저조건
	answer++;
    return;
}
for(int i=1;i<=2;i++){
	if(sum<=n){
    	sum+=i;
        dfs(sum,n);
        sum-=i;
    }
}

 

이렇게 코드 구현했더니.

7번부터 시간 초과...와 숫자가 크면 시간이 어마어마한것을 보았다...!

 

그래서 다시 문제를 보기 시작함.... 역시

1일경우
[1] → 1가지

2일 경우
[1,1],  [2] → 2가지

3일 경우
[1,1,1],  [1,2],  [2,1] → 3가지

4일 경우
[1,1,1,1],  [1,1,2],  [1,2,1],  [2,1,1],  [2,2] → 4가지

엇? 먼가 규칙이 보이지 않는가? 

2일 경우
[1,1],  [2] → 2가지

3일 경우
[1,1,1],  [1,2],  [2,1] → 3가지

4일 경우
[2,2],  [1,1,2],  [1,1,1,1],  [1,2,1],  [2,1,1],   → 5가지

그럼 5일 경우도 한번 해보면 될 것이다.. 아마... 그 예상 적중일 거임...

dp[i] = dp[i-1] + dp[i-2]; 

근데 또 1 1 2 3 5 .. 이거랑 위에 공식 어디서 보지 않았삼?

정답: 피보나치수열 

그래서 피보나치 수열 방식으로 코드 구현하면 끗 

또한, % 1234567 계산하는 거 위치 조심하세요~  이전 값을 항상 활용한다는 점!

시간 훨씬 단축됐죠? 역시 Dp의 힘!

 

 

3. 코드

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

 

 

피드백은 언제나 환영입니다 :) 🌳