문제

문제 링크

어떻게 접근할 것인가

코드

#include <cstdio>
using namespace std;

int n, w[303], d[303][2];

int main(){

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    d[1][0] = d[1][1] = w[1];
    d[2][0] = d[2][1] = w[2];
    for(int i = 1; i <= n; i++){
        //한칸전에서 왔다면 두칸 이동한 위치 업데이트
        if(d[i][0] + w[i + 2] > d[i + 2][0])d[i + 2][0] = d[i][0] + w[i + 2];
        if(d[i][0] + w[i + 2] > d[i + 2][1])d[i + 2][1] = d[i][0] + w[i + 2];
        //두칸전에서 왔다면 한칸 이동하여 한칸 정보 업데이트하고, 두칸 이동한 위치 모두 업데이트
        if(d[i][1] + w[i + 1] > d[i + 1][0])d[i + 1][0] = d[i][1] + w[i + 1]; 
        if(d[i][1] + w[i + 2] > d[i + 2][0])d[i + 2][0] = d[i][1] + w[i + 2];
        if(d[i][1] + w[i + 2] > d[i + 2][1])d[i + 2][1] = d[i][1] + w[i + 2];
    }
    printf("%d", d[n][0] > d[n][1] ? d[n][0] : d[n][1]);
}

느낀점