[Baekjoon] 16493번: 최대 페이지 수

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

16493번: 최대 페이지 수

 

---

 

문제 해결 과정

착안

이전 포스트에서와 동일한 원리로, 동적계획법(dynamic programming)에 기반하여 문제를 해결하였다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

struct Chapter
{
	int Days;
	int Pages;
};

Chapter Chapters[20];
int DP[201];

int main()
{
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
		cin >> Chapters[i].Days >> Chapters[i].Pages;

	for (int i = 0; i < M; i++)
		for (int m = N; m >= Chapters[i].Days; m--)
			if (m == Chapters[i].Days || DP[m - Chapters[i].Days] > 0)
			{
				int valueSum = DP[m - Chapters[i].Days] + Chapters[i].Pages;
				if (DP[m] < valueSum)
					DP[m] = valueSum;
			}

	cout << *max_element(DP, DP + N + 1) << "\n";
	return 0;
}

 

실행 결과