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

문제

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

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

 

풀이 코드

public long solution(int n) {           //멀리 뛰기
    long answer = 0;
    long f = 1;
    long s = 2;
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        for (int i = 3; i <= n; i++) {
            answer = (f + s) % 1234567;
            f = s;
            s = answer;
        }
        return answer;
    }

}

이 문제는 풀어보면 생각보다 간단하다.

n = 1일때부터 n = 4일때까지 간단히 예시를 들어보겠다.

n = 1일때 -> (1)

n = 2일때 -> (1+1),(2)

n = 3일때 -> (1+2),(1+1+1),(2+1)

n = 4일때 -> (1+1+2),(2+2),(1+2+1),(1+1+1+1),(2+1+1)

여기서 보면 색으로 구분해놔서 알아보기 쉬운데 보면

n일때 나올 수 있는 방법은 n-1에서 나올 수 있는 방법에 1칸 추가 + n-2에서 나올 수 있는 방법에 2칸 추가이고

n일때 경우의 수는 n-1일때 경우의 수 + n-2일때 경우의 수가 된다.

근데 숫자가 너무 커지는 것을 방지해서 문제에서 1234567을 나눠주라고 했으므로 %1234567을 한 것이고,

그래서 코드가 위와 같이 나온다.