99클럽 코테 스터디 22일차 TIL , 멀리 뛰기

문제

풀이

n이 입력으로 들어왔을 때, 한 칸 혹은 두 칸을 움직여서 갈 수 있는 방법의 개수를 찾으면 된다.

규칙을 찾으면 되는 문제인데, 처음에 생각하기를 1칸씩만 움직여서 가는 방법에서 거기서 선택해서 두 칸을 가는 방법으로 바꿔주면 된다고 생각했다. 방법의 개수를 찾는 데에는 적당한 방법이었으나 결과적으로는 그걸 찾는 방법이 아니었다. n = 1 일 때, (1)... 1개

n = 2 일 때, (1,1), (2) ... 2개

n = 3 일 때, (1,1,1), (2,1), (1,2)... 3개

n = 4 일 때, (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2)... 5개

n = 5 일 때, (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)... 8개

f(n) = f(n-1) + f(n-2) 의 점화식을 가진다. 피보나치 수와 똑같다. 해서 풀이도 같다.

제출 1 - 정답

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

TIL

• DP (동적계획법)