취미로 코딩하기

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

이번에 볼 문제는 백준 1940번 문제인 주몽이다.

문제는 아래 링크를 확인하자.

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

갑옷 조합의 경우의 수를 구하는 문제가 아닌 갑옷을 최대 몇 개 만들 수 있는지를 구하는 문제임에 주의하자.

고유번호가 M인 갑옷을 만드는 재료의 고유번호는 k와 M-k의 형태로만 이루어질 수 있다는 점을 이용하여 크기 1000만의 배열을 작성하면 문제를 간단히 해결할 수 있다.

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

#include <iostream>
using namespace std;

int arr[10000001];

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

	int ans = 0;
	int N, M; cin >> N >> M;
	while (N--) {
		int x; cin >> x;
		arr[x]++;
	}
	if ((M & 1) == 0) {
		int& tmp = arr[M / 2];
		ans += tmp / 2;
		int MM = M / 2;
		for (int i = 1; i < MM; i++) {
			ans += min(arr[i], arr[M - i]);
		}
	}
	else {
		int MM = M / 2;
		for (int i = 1; i <= MM; i++) {
			ans += min(arr[i], arr[M - i]);
		}
	}

	cout << ans;
}