프로그래머스 - 12914: 멀리 뛰기 - 문제 풀이 접근법 및 자바 정답 풀이

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

프로그래머스

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이란 타켓을 가져서 1111 ,121, 112, 211 처럼 순열과 같은 dfs 로 풀어야하나, 고민을 했습니다. 하지만 제한사항을 보면 n 은 2000 이고 이런 시도는 잘 못된 걸 알 수 있었죠.

 

이 문제는 풀이법은 아주 쉬운 문제이지만, 이 풀이법을 떠올리는 게 더 어려운 문제인 것 같습니다.

먼저 문제 풀이 접근법을 말씀드리자면, 이 문제는 dp로 풀어야합니다. 

 

DP를 사용할 수 있는 문제의 예시
1. 피보나치 수열: 피보나치 수열의 n번째 값을 계산할 때 F(n) = F(n-1) + F(n-2) 형태로 정의되며, DP로 효율적으로 계산할 수 있습니다.
2. 최소 경로 문제: 예를 들어, 2차원 격자에서 좌상단에서 우하단까지 가는 경로의 최소 비용을 구하는 문제는 DP로 해결할 수 있습니다.
3. 동전 교환 문제: 주어진 금액을 만들기 위해 필요한 최소 동전의 수를 구하는 문제도 DP로 해결할 수 있습니다.

 

이 중 이문제는 피보나치 수열을 활용하여 풀어야하는 문제입니다.

 

풀이의 점화식은 다음과 같습니다.

dp[n] = dp[n-1] + dp[n-2]

 

효진이가 n번째 칸에 도달하는 방법은 다음 두 가지로 나뉩니다.

1. n-1번째 칸에서 1칸 뛰어서 도착한 경우
2. n-2번째 칸에서 2칸 뛰어서 도착한 경우
이 두 가지 방법을 합치면, n번째 칸에 도달하는 총 방법의 수를 구할 수 있습니다. 따라서 n번째 칸에 도달하는 방법의 수는 dp[n-1] (1칸 뛰기)와 dp[n-2] (2칸 뛰기)의 합입니다.

 

예를 들어 효진이가 4번째 칸에 도달하는 방법은 3번째 칸에서 한 칸 움직이는 방법과 2번째 칸에서 두 칸 움직이는 방법 2가지가 있다는 것입니다.

정답 풀이

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

 

먼저 n이 2000 이하 자연수이므로 1과 2일때 경우를 생각해 줘야합니다. 점화식은 n -1 과 n - 2로 세우기 때문에 첫 수가 3이기 때문입니다. 만약 n이 3이상 2000이하였다면 이 과정이 필요가 없습니다.

 

반복문에선 모듈러 연산이 쓰입니다. 어떤 값을 나눈 나머지와 또 그 나머지를 더하면 두 수를 더한 것과 어떤 값을 나눈 나머지가 같아집니다. 예를 들어 보겠습니다.

9 % 5 = 4
19 % 5 = 4

28 % 5 = 8 % 5

 

나머지 4와 나머지 4를 더하고 다시 5로 나누어도 9와 19의 합을 5로 나눈 나머지와 같아지죠.

잘 이해가 안되시는 분은 구글에 모듈러 연산을 검색해보시면 더욱 자세한 설명을 찾으실 수 있습니다.

 

정답 풀이는 너무 간단하죠? 하지만 이 풀이를 저도 첨엔 떠올리지 못하여 리마인드할 겸 이렇게 글을 남겨봅니다.

 

 

 

 

이 문제와 완전 비슷한 문제가 하나 더 있는데, 같이 첨부하도록 하겠습니다.

이 문제로 다시 한 번 시도해보세요.

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

프로그래머스