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

17 Oct 2022 in Study on Coding Test

기초적인 DP문제(아마도)

정답제출코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

long long dp[2000];

long long solution(int n) {
    long long answer = 0;
    
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n ; ++i)
    {
        dp[i] = dp[i-1] % 1234567 + dp[i-2] % 1234567;
    }
    
    answer = dp[n] % 1234567;
    
    return answer;
}

소스코드 설명

• 기본 세팅에 vector가 있었지만 사실 vector는 필요 없음.
  

• 피보나치 수열 for문으로 푸는거랑 원리가 같음.

• 이전 칸수 + 이전 전 칸수의 값이 곧 현재 칸 수까지의 경우의 수와 같아짐.

• 1234567로 나눈 나머지는 반환하라고 했으므로 % 1234567 연산을 진행함.