BOJ 5721 - 사탕 줍기 대회

문제 링크(Link)

---

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

문제 해결 (Solution)

---

 1. i번 째 행은 i+2행과는 아무 상관이 없다. i행의 열 중에서 서로 인접하지만 않으면 된다.

 2. 1의 조건을 만족시키는 DP table을 생각해보면, 행에 대한 DP와 열에 대한 DP를 따로 만들어 해결하는 게 편함.

 3. dp1[i] = i행에서의 최대값.

    dp2[j] = i행에서 열들을 선택했을 때의 가장 큰 값.

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 처음엔 행과 열을 따로 생각할 수 있다는 생각을 하기 어렵다. 이런 유형이 있다는 것을 알아야한다.

 2. 행과 열의 크기가 주어지지 않으므로, 그냥 1차원 배열로 생각하고 인덱스를 잘 다뤄야한다.

참고(Reference)

---

 - 아이디어를 받은 Blog : http://sungwoo91.tistory.com/15

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<iostream>
	#include<cstdio>
	#include<string>
	#include<cstring>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<ctime>
	#include<vector>
	using namespace std;
	int N,M;
	// caution 1, 2
	int a[100003];
	int dp1[100003],dp2[100003];
	int go2(int n,int m){
	if(n>=M*(m+1))
	return 0;
	int& ret = dp2[n];
	if(ret!=-1) return ret;
	ret = max(go2(n+2,m)+a[n],go2(n+1,m));
	return ret;
	}
	int go1(int n){
	if(n>=N)
	return 0;
	int& ret = dp1[n];
	if(ret!=-1) return ret;
	ret=max(go1(n+2)+go2(n*M,n),go1(n+1));
	return ret;
	}
	int main(){
	while(true){
	memset(dp1,-1,sizeof(dp1));
	memset(dp2,-1,sizeof(dp2));
	cin >> N >> M;
	if(N==0&&M==0)
	break;
	for(int i=0;i<N*M;i++){
	scanf("%d",&a[i]);
	}
	printf("%d\n",go1(0));
	}
	return 0;
	}

view raw BOJ 5721.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.