문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는(1칸, 1칸, 1칸, 1칸)(1칸, 2칸, 1칸)(1칸, 1칸, 2칸)(2칸, 1칸, 1칸)(2칸, 2칸)의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한 사항
•
n은 1 이상, 2000 이하인 정수입니다.
입출력 예
입출력 예 설명
입출력 예 #1위에서 설명한 내용과 같습니다.
입출력 예 #2(2칸, 1칸)(1칸, 2칸)(1칸, 1칸, 1칸)총 3가지 방법으로 멀리 뛸 수 있습니다.
나의 풀이
class Solution {
public long solution(int n) {
long[] arr = new long[n + 1];
arr[0] = 1;
arr[1] = 1;
for(int i = 2; i <= n; i++) {
arr[i] = (arr[i - 1]+ arr[i - 2]) % 1234567;
}
return arr[n];
}
}
Java
복사
Remark
•
처음에 경우의 수 문제인줄 알고 순열과 조합으로 풀었다가 틀린 문제. 모르겠어서 구글에서 정답 찾아봄
•
DP문제(피보나치 수열)
◦
효진이가 어떤 지점에 도착했다면 그 전에 한 번에 2칸을 뛰어서 도착했거나, 1칸만 뛰어서 도착했을 것임
◦
어찌 됐든 두 가지 출발 지점은 또 각각 그곳에 도착하는 경우의 수를 가지고 있었을 것이고, 따라서 두 경우의 수를 단순히 합치면 도착 지점의 경우의 수가 됨