99클럽 코테 스터디 22일차 TIL - [프로그래머스] 멀리 뛰기 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 멀리 뛰기 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/12914

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 멀리뛰기에 사용될 칸의 수 n (1 ≤ n ≤ 2000)
출력 : 끝에 도달하는 방법 % 1234567

가능한 시간복잡도

O(n)

알고리즘 선택

dp

📌 코드 설계하기

1. 모듈러 연산을 위한 변수를 초기화한다.
2. n이 1이나 2일 경우 바로 반환하도록 초기값을 설정한다.
3. 동적 계획법을 위한 배열 dp를 초기화한다.
4. 초기 조건을 설정한다.
5. 피보나치 수열을 이용해 dp의 값을 넣는다.
6. dp[n]를 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

class Solution {
    public long solution(int n) {
        // 모듈러 연산을 위한 변수
        int MOD = 1234567;

        // n이 1이나 2일 경우 바로 반환할 수 있도록 초기값 설정
        if (n == 1) return 1;
        if (n == 2) return 2;

        // 동적 계획법을 위한 배열 선언
        long[] dp = new long[n + 1];

        // 초기 조건 설정
        dp[1] = 1;
        dp[2] = 2;

        // 피보나치 수열의 변형으로 문제 해결
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        // n번째 방법의 수 반환
        return dp[n];
    }
}