[Codility] NumberSolitaire

#include <algorithm>
using namespace std;

int solution(vector<int> &A) {
    int answ;
    int n=A.size();
    vector<int> dp(n);
    dp[0]=A[0];
    for(int i=1; i<n; i++){
        int best=dp[i-1];
        for(int k=2; k<=6; k++){
            if(i-k>=0){
                best=max(best, dp[i-k]);
            }
        }
        dp[i]=best+A[i];
    }
    return dp[n-1];
}

 

문제) 0번 칸에서 시작해서 주사위(1~6)로 이동하면서, 밟은 칸 숫자의 합의 최댓값을 구하라

 

DP 아이디어)

dp[i] = i번 칸에 도착했을 때 얻을 수 있는 최대 점수, i번 칸은 i-1 ~ i-6 중 어디에서 왔을 수 있음

dp[i] = A[i] + max(dp[i-1] ~ dp[i-6])

best = "지금까지 발견한 최고 dp 값"

best 갱신: 지금까지 봤던 후보(best)랑 i-k에서 오는 경우 중 더 좋은 걸 best로 하자

 

정리)

for (i = 1 to N-1):
    i로 올 수 있는 이전 칸들(dp[i-1] ~ dp[i-6]) 중
    가장 점수가 큰 것을 찾고
    거기에 A[i]를 더한다