취미로 코딩하기

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

이번에 볼 문제는 백준 14718번 문제인 용감한 용사 진수이다.
문제는 아래 링크를 확인하자.

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

진수가 스탯을 힘 능력치에 $X$만큼 투자할 경우, X 이하의 힘 능력치를 요구하는 병사 중 가장 높은 값으로 X의 값을 바꿔도 상대할 수 있는 병사의 수는 변하지 않음을 관찰하자. 이러한 관찰은 민첩, 지능 등 다른 능력치에도 동일하게 적용된다.

위의 관찰을 통해 가장 효율적으로 스탯을 배분하는 방법은 각 스탯을 병사의 스탯 중 하나의 값으로 투자하는 것임을 알 수 있다. 이러한 스탯 투자방법은 $N^3$ 가지 존재하고, 각 경우마다 병사 $K$명을 상대할 수 있는지의 여부는 300번의 비교를 통해 확인할 수 있다. 이는 이 문제를 해결하기에 충분한 연산 수이다.

위의 내용을 구현한 코드를 제출해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, K;
int STR[100], DEX[100], INT[100];
int enemy[100][3];
int ans = 1000000007;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> enemy[i][0] >> enemy[i][1] >> enemy[i][2];
		STR[i] = enemy[i][0], DEX[i] = enemy[i][1], INT[i] = enemy[i][2];
	}

	for (int s = 0; s < N; s++) {
		int& ss = STR[s];
		for (int d = 0; d < N; d++) {
			int& dd = DEX[d];
			for (int i = 0; i < N; i++) {
				int& ii = INT[i];
				int cnt = 0;
				for (int k = 0; k < N; k++) {
					if (ss < enemy[k][0] || dd < enemy[k][1] || ii < enemy[k][2]) continue;
					cnt++;
				}

				if (cnt >= K) ans = min(ss + dd + ii, ans);
			}
		}
	}

	cout << ans;
}