취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5721번 문제인 사탕 줍기 대회이다.
문제는 아래 링크를 확인하자.

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

문제의 조건을 잘 생각해보면, 하나의 행에서 어떤 사탕을 고른다면 그 행에서 서로 인접하는 칸이 없도록 칸을 골라 최대 개수의 사탕을 주울 수 있다는 점을 알 수 있다.

각 행별로 주울 수 있는 최대 개수를 고른다면, 행단위로 "고를 행과 안 고를 행"을 선택하는 것으로 최대로 주울 수 있는 사탕의 개수를 알 수 있다. 방식은 한 행에서 주울 수 있는 최대 사탕의 개수를 구하는 것과 완전히 같다.

가능한 행, 열의 개수의 최댓값이 각각 10만이므로 10만 by 10만 크기의 배열을 선언하는 것은 무리이다.

필요한 만큼만 선언하고 계산하는 방식으로 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int cols[100000];
int rows[100000];
int dp[100000];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int R, C; cin >> R >> C;
	while (R > 0) {
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) cin >> cols[c];
			if (C == 1) {
				rows[r] = cols[0];
				continue;
			}
			dp[0] = cols[0], dp[1] = max(cols[0], cols[1]);
			for (int i = 2; i < C; i++) {
				dp[i] = max(dp[i - 1], dp[i - 2] + cols[i]);
			}
			rows[r] = dp[C - 1];
		}
	
		if (R == 1) cout << rows[0] << '\n';
		else {
			dp[0] = rows[0], dp[1] = max(rows[0], rows[1]);
			for (int i = 2; i < R; i++) {
				dp[i] = max(dp[i - 1], dp[i - 2] + rows[i]);
			}
			cout << dp[R - 1] << '\n';
		}

		cin >> R >> C;
	}
}