[BOJ/백준][Gold4] 5721 : 사탕 줍기 대회 (C++)

https://www.acmicpc.net/problem/5721

5721번: 사탕 줍기 대회

 

[난이도] Gold4
[유형] DP

[풀이]
어떤 칸 (r,c) 의 한 숫자를 선택할 경우 어차피 r-1,r+1행은 선택할 수가 없습니다.
그러므로 r행의 숫자들을 선택할 때 이왕이면 최대한 많은 사탕을 선택하는 것이 좋습니다.

r행에서 선택할 수 있는 사탕의 최댓값은 dp를 이용해 구할 수 있습니다.
그리고 구한 값을 maxv 배열에 저장해 놓은 뒤

이 배열의 값을 이용해 같은 방식으로 어떤 열이 선택되는지를 dp로 구해주면 됩니다.
dp2[r] : r행을 선택 했을 때, 얻을 수 있는 사탕의 최대 개수.
dp2[r] = maxv[r]+max(dp2[r+2],dp2[r+3]);

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
using namespace std;
int M,N,board[200000],dp1[200000],dp2[200000],maxv[200000];
int sol(int r,int c){
    if(c>=N) return 0;
    int& ret = dp1[r*N+c];
    if(ret!=-1) return ret;
    return ret=board[r*N+c]+max(sol(r,c+2),sol(r,c+3));
}
int sol2(int r){
    if(r>=M) return 0;
    int& ret =dp2[r];
    if(ret!=-1) return ret;
    return ret=maxv[r]+max(sol2(r+2),sol2(r+3));
}
int main(){
    while(1){
        scanf("%d%d",&M,&N);
        if(N==0 && M==0) break;
        memset(dp1,-1,sizeof(dp1));
        memset(dp2,-1,sizeof(dp2));
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                int v;
                scanf("%d",&v);
                board[i*N+j]=v;
            }
            maxv[i] = max(sol(i,0),sol(i,1));
        }
        printf("%d\n",max(sol2(0),sol2(1)));
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/5721.cpp