문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.
입출력 예
n result
4 5
3 3
입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.
풀이
코딩테스트 문제를 풀 때마다 어떻게 접근해야 할까? 고민을 하게 되는데
이 문제는 규칙이 알뜻 말뜻하여 일단 손으로 노가다하여 규칙을 발견했다.
n=1 / 값=1
n=2 / 값=2
n=3 / 값=3
n=4 / 값=5
n=5 / 값=8
n=6 / 값=13
빠르게 n=6일 때까지 경우의 수를 구해보니 n끼리의 규칙이 아닌 n의 값들의 규칙이 보였다.
첫번째, 값=2부터(n=2부터) 1, 2, 3, 4, 5 씩 증가하는 것
두번째, (값=1)+(값=2) = (값=3) / (값=2)+(값=3) = (값=5)
즉 An = A(n-2)+A(n-1) 인 것이다.
대신, n=1일때와 n=2일 때는 값이 1씩 증가하기에 고정값을 주고 n=3부터 반복문을 돌리면 뭔가 나올 것 같다.
public long solution(int n) {
// 1<=n<=2000 총 2000칸이 필요하기에 배열의 크기를 2000으로 주어 생성
long[] jp = new long[2000];
// n=1, n=2 의 값을 고정한다. (n=2부터 값이 1씩 증가)
jp[1]=1;
jp[2]=2;
// n=3부터 반복문을 돌려 해당 값을 구한다.
for(int i=3; i<=2000; i++) {
jp[i] = jp[i-2] + jp[i-1] % 1234567;
}
return jp[n];
}풀다보니 중학교 때 배운 피보나치수열이었다는 것이 생각났다.
개념을 알더라도 이를 코드로 구현하여 답을 구하는 것은 쉽지 않다.
그리고 더 찾아보니 위 같은 문제를 알고리즘에서 dp라고 한다고 한다.
이 부분은 알고리즘 공부할 때 찾아 포스팅 할 예정이다!
