알고리즘
[프로그래머스] 멀리뛰기
yujeong kang
2021. 1. 26. 20:34
[프로그래머스] level3 멀리뛰기
소요시간 : 7분
종이에 적으니까 규칙이 보이길래 코드 짜봤더니 통과 되었다.
n번째 칸은 n-1번째와 n-2번째 칸의 경우를 더하면 나왔기 때문.
왜냐면 한 칸과 두 칸, 움직이는 경우가 2가지니까!
처음엔 문제만 보고 뭔가 dp 문제 아닐까 했는데 풀고나서
다른 사람들 풀이를 보니 dp 풀이도 있고 피보나치 풀이도 있고 다양하구만
class Solution {
public long solution(int n) {
if(n == 1 || n == 2) return n;
long[] arr = new long[n+1];
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i < arr.length; i++) {
arr[i] = ((arr[i-2] % 1234567) + (arr[i-1] % 1234567)) % 1234567;
}
return arr[n] % 1234567;
}
}