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

 

프로그래머스

 

풀이

목적지에 갈 수 있는 방법의 수에 규칙이 있을 것이라 생각이 되어 규칙을 찾아보기로 했습니다.

// 거리 1일 때 방법 1개
1

// 거리 2일 때 방법 2개
1 1
2

// 거리 3일 때 방법 3개
1 1 1
2 1
1 2

// 거리 4일 때 방법 5개
1 1 1 1
2 1 1
1 2 1
1 1 2
2 2

// 거리 5일 때 방법 8개
1 1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
2 2 1
2 1 2
1 2 2

// 거리 6일 때 방법 13개
1 1 1 1 1 1
2 1 1 1 1
1 2 1 1 1
1 1 2 1 1
1 1 1 2 1
1 1 1 1 2
2 2 1 1
2 1 2 1
1 2 2 1
1 2 1 2
1 1 2 2
2 1 1 2
2 2 2

 

이렇게 만 본다면 거리별로 각각
1 2 3 5 8 13이라는 방법의 수를 가지고 있음을 확인할 수 있었습니다.

num[i] = num[i-1]+num[i-2]

라는 규칙을 볼 수 있습니다. 해당 규칙을 문제에 적용하여 보아 아래와 같은 코드를 작성하였습니다. 그리고 문제에서 주어진 답이 1234567을 나눈 나머지를 구하는 것이기 때문에, 모듈러 연산을 적용해 줍니다.

Code

class Solution {
    public long solution(int n) {
        long answer = 0;
        final int DIV = 1234567;
        int a = 0;
        int b = 1;

        int count = 0;
        while(count < n){
            int c = (a+b)%DIV;
            a = b%DIV;
            b = c;
            count++;
        }

        return b;
    }
}

 

통과!