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

[문제 설명]

programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기

 

[풀이 내용]

* 사용 알고리즘 : DP 

 

1. brute force알고리즘을 사용해서 중복 순열로 풀면 시간초과가 뜬다. 

문제의 규칙을 찾아보니 피보나치 수열과 같았다. 

 

1) 1칸일 때 -> 1가지  

- 1칸  

 

2) 2칸일 때  -> 2가지

- 1칸 1칸

- 2칸 

 

3) 3칸일 때 -> 3가지 

- 1칸 1칸 1칸

- 1칸 2칸

- 2칸 1칸

 

4) 4칸일 때  -> 5가지 

- 1칸 1칸 1칸 1칸 

- 1칸 1칸 2칸

- 1칸 2칸 1칸

- 2칸 1칸 1칸 

- 2칸 2칸

 

...

 

∴ 1 2 3 5 8 13 ...

 

2. 모듈러 연산 

문제에서  끝에 도달하는 총 방법의 수에서 1234567를 나눈 나머지를 return하라고 한다. 

문제풀이를 꽤 하다보니 이런 조건을 주는 이유와 풀이 방법에 대해서 알고 있다. 

이런 조건을 주는 이유는 정답값이 return 타입인 long의 숫자 범위를 초과하지 못하도록 하기 위함이고, 풀이방법으로는 모듈러 연산을 사용하면 된다. 

 

모듈러 연산법을 간단하게 써보면 다음과 같다 .

a = (b + c) 라면 다음 식을 만족한다. 

a % m = (b%m + c%m) % m

 

느낀점 : Level3라고 하기엔 코드가 너무 단순해서 당황스러웠다. 

 

[JAVA code]

package com.algorithm.programmers.level3;

public class Test10 {

    public static long answer = 0;

    public static void main(String[] args) {
        System.out.println("solution=" + solution(1));
    }

    public static long solution(int n) {
        long answer = 0;
        int divide = 1234567;

        int[] fib = new int[n+2];
        fib[1] = 1;
        fib[2] = 2;

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