프로그래머스 Lv.3) 멀리 뛰기

멀리 뛰기

코딩테스트 연습 - 멀리 뛰기

풀이

dp 문제이고, 피보나치 문제임을 바로 눈치챘다. 바로 1차원 배열을 만들어서 제출했는데, 1번 문제가 틀렸다고 나왔다. 피보나치 문제가 아닌가? 생각에 다시 문제를 꼼꼼히 봤으나 피보나치가 맞았다. 문제점을 모르겠어서 질문하기 탭을 확인했는데, n만큼 배열을 만들면 메모리 초과가 뜬다는 것이었다... 충격.. 최대 n이 고작 2000인데 메모리 초과가 난다.. 아무튼 그래서 변수 두개를 이용하기로 했다.

answer는 계속 최신화 시켜주면서 n-1 n-2의 값을 바꿔가는 것이다.

 

로직

1. 답을 리턴할 변수 answer와 n-1, n-2 값을 담아줄 left, right를 선언한다.

2. n까지 반복문을 통해 answer에 답을 담아준다. 또한, left와 right를 n-1, n-2에 맞게 각각 다시 값을 넣어준다.

 

코드

class Solution {
    int MOD = 1234567;
    public long solution(int n) {   // 배열 dp ~> 변수 세개
        long answer = 0;
        long left =1;
        long right =2;
        if(n ==1) {
            answer = left;
        } else if (n==2) {
            answer = right;
        } else {
            for(int i=2; i<n; i++) {
                answer = (left + right)%MOD;
                left = right;
                right = answer;
            }
        }
        return answer;
    }
}