Algorithm/problem

백준 1535번:안녕 -냅색(배낭)문제 C++

DingCoDing 2022. 1. 27. 15:18
반응형

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

 

1535번: 안녕

첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번

www.acmicpc.net

 

 

다이나믹프로그래밍이자 냅색 문제이다.

문제 조건에 따라 체력은 100이 되면 안되서 99가 최대이다.

 

 

#include <bits/stdc++.h>
using namespace std;

int n, cost[21], point[21], dy[101];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> point[i];
	}

	for (int i = 0; i <n; i++) {
		for (int j = 100; j >= cost[i]; j--) {
			dy[j] = max(dy[j], dy[j - cost[i]] + point[i]);
		}
	}

	cout << dy[99];

}

백준 1535번 안녕 

 

반응형