[Programmers/프로그래머스 lv2][C++] 멀리 뛰기

문제

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

프로그래머스 멀리 뛰기

 

문제 내용

한 번에 갈 수 있는 칸은 1칸 또는 2칸이다.

n번째 칸까지 가려고 할 때, 도달하는 방법이 몇 개인지 구하면 된다. (단, 1234567로 나눈 나머지를 구할 것)

 

문제 풀이

문제를 보자마자 dp를 떠올렸다.

문제를 풀기 위해 n=5일 때까지의 가짓수를 모두 적어보았다.

프로그래머스 멀리 뛰기 풀이

위의 사진과 같이, n-1칸까지 뛰고, +1칸 가는 것 경우와 n-2칸까지 뛰고, +2칸 가는 경우로 나눌 수 있다.

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {

    int dp[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];
}

 

문제 코드 설명

1234567로 나누는 것을 잊지 말자.

+) 문제에서 주어질 때에는 long long으로 세팅이 되어있지만, 1234567로 계속해서 나머지 연산을 하기 때문에 int를 사용해도 오버플로우가 발생하지 않는다.