[프로그래머스] 자바(Java) - 멀리 뛰기

🧩 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

💡내가 작성한 코드

• 한 번에 1칸 또는 2칸을 뛸 수 있다는 조건이 피보나치 수열의 점화식과 동일하게 작용
  • n번째 칸에 도달하는 방법은 (n - 1) 번째 칸에서 1칸 뛰는 방법 과 (n - 2) 번째 칸에서 2칸 뛰는 방법 이 존재

class Solution {
    public long solution(int n) {
        long[] arr = new long[n + 2];
        arr[1] = 1;
        arr[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
        }
        
        return arr[n];
    }
}

1. 배열 생성 및 초기화
   • `n + 2` 만큼 초기 배열을 선언하는 이유는 계산 과정에서 모든 인덱스 접근이 가능하게 하도록 배열 길이를 넉넉히 설정
   • 필요한 모든 경우의 수를 저장하기 위함
2. for 문을 통해 점화식 적용
   • `n`이 1 또는 2일 경우에는 반복문을 실행할 필요없이 바로 답을 반환할 수 있기 때문에 `n`이 3 이상일 때부터 반복문 실행
     • `n`이 1일 경우, 1칸을 한 번 뛰는 방법만 존재 -> 값은 1
     • `n`이 2일 경우, 1칸씩 두 번 뛰는 방법과 한 번에 2칸 뛰는 방법만 존재 -> 값은 2
   • `arr[i] = (arr[i - 1] + arr[i - 2])` 점화식을 사용하여 현재 칸에 도달하는 방법을 계산 후, 문제에서 주어진 조건인 1234567 로 나눈 나머지를 저장 후 결과값 반환

 

🧠 배운 점

1. 문제를 보고 피보나치 수열의 점화식을 이용하여 접근하면 되는구나를 깨달음
   • 문제에서 주어진 "한 번에 1칸 또는 2칸을 뛸 수 있다" 라는 조건을 보고 피보나치 수열의 점화식과 유사하다는 것을 판단할 수 있게 되었다.
2. 반복문을 통한 피보나치 수열의 점화식 풀이
   • 재귀적인 방법 뿐만 아니라 반복문을 이용하여 효율적으로 해결할 수 있음을 배움