멀리 뛰기/C++

멀리 뛰기 - 프로그래머스

프로그래머스

칸이 1개일 때 (1)

칸이 2개일 때 (1,1), (2)

칸이 3개일 때 (1,2), (2,1), (1,1,1)

칸이 4개일 때 (1,1,2), (2,2), (1,2,1), (2,1,1), (1,1,1,1)

 

자세히 보면 칸이 n개일 때 뛸 수 있는 방법은 n-1의 방법에 1씩 추가한 방법 + n-2의 방법에 2씩 추가한 방법이란 걸 알 수 있다.

즉, 동적 계획법(Dynamic Programming)으로 풀면 되는 문제이다.

식으로 작성하면 DP[n] = DP[n-1] + DP[n-2]라는 피보나치 수열의 형태가 된다.

 

풀이 방법

1. int형 벡터인 con을 선언한다.

2. con[0]과 con[1]에 1을 담는다.

3. con[i -1] + con[i - 2] % 1234567를 i가 n이 될 때까지 con에 push_back()한다.

4. 반복문이 끝난 후 con.back()을 리턴

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {
    long long answer = 0;
    
    vector<int> con;
    
    con.push_back(1); con.push_back(1);
    
    for(int i = 2; i <= n; i++) {
        con.push_back((con[i - 1] + con[i - 2]) % 1234567);
    }
    
    answer = con.back();
    
    return answer;
}