🔥[99클럽 코테 스터디] 22일차 TIL - 멀리 뛰기

⏳문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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가지 방법으로 멀리 뛸 수 있습니다.

---

✏️풀이

규칙을 찾기 위해 총 칸이 1칸일 때부터 5칸일 때까지 나올 수 있는 모든 경우의 수를 한 번 적어보았다.

여기서 찾은 규칙은, 총 칸이 N인 경우 N-1칸일 때 경우의 수와 N-2칸일 때 경우의 수의 합이라는 것이다.

예를 들어, 총 4칸일 때의 모든 경우의 수는 2칸일 때 모든 경우의 수 + 3칸일 때 모든 경우의 수이다.
이 규칙에 Dynamic Programming을 적용시켜 구현을 해 보았다.

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

중복되는 계산의 범위를 줄이기 위해 배열을 하나 생성해주었고,
총 칸이 1인 경우에 1을, 2인 경우에 2를 미리 저장해 주었다.

그리고 총 칸이 3인 경우부터 n칸인 경우까지 위에서 찾은 규칙을 적용해 주면 문제를 해결할 수 있..

는 줄 알았다.

런타임 에러라 배열의 크기에 문제가 있나 싶어,

long[] dp = new long[2000];

배열을 생성할 때 크기를 n+1대신, 2000이라는 상수값을 넣어주니

문제가 해결되었다!

n으로 1이 들어올 때

dp[2] = 2;

이 라인에서 2번 인덱스에 접근할 수 없었기 때문이었다.
앞으론 초기값 설정할 때 주의하기..!

---

🔗문제 링크
💻Repository