프로그래머스 (멀리뛰기_JAVA)

문제 설명

1칸또는 2칸을 뛰어서 n개의 수가 주어질때 도달하는 방법 가짓수를 구하는 문제

문제 풀이 방법

배열의 길이가 달라지므로 ArrayList를 적용한다
배열에 1 또는 2를 넣고 그 합이 n과 같아야 한다
최대길이는1칸씩 n개, 최소길이는 2칸씩 n/2개이다(n이 홀수일 경우 반올림)
sum 변수에 방법 가짓수를 더해주고 1234567을 나눈 나머지를 리턴한다.
처음엔 홀수와 짝수일때로 나눠서 생각했는데 너무 복잡해졌다.
잘 모르겠어서 다른사람코드를 살펴보니 피보나치수열로 풀었는데 이해가 안갔다..ㅜㅜ
왜지. 한참 고민해보니.. 피보나치가 맞았다.ㅎ
패턴을 나열해서 보면 피보나치 수열임을 확인할 수 있다. 1 - 1 - 2 - 3 - 5 - 8 - 13 즉, 전전 값과 전 값을 더하면 다음의 값을 유추해 낼 수 있고, 3번째부터 전전 값의 존재하므로 이전의 길이를 요구하는 답은 바로 정답을 리턴시키는 로직으로 만들었다.

public class 멀리뛰기 {
public long solution(int n) {
long answer = 0;
if (n==1) {
return 1;
}if (n==2) {
return 2;
}return (solution(n-1)+ solution(n-2))%1234567;

    }
}

이렇게 작성했는데 실패.. 시간초과.
다시...ㅠ 배열로 해보장

public class 멀리뛰기 {
public long solution(int n) {
long arr []= new long[2001];

	 arr[1]=1;
	 arr[2]=2;
	 
	 for(int i=3; i<2001; i++) {
		 arr[i] = (arr[i-1]+arr[i-2])%1234567;			 
	 }		 
	 return arr[n];
    }
}