취미로 코딩하기

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

이번에 볼 문제는 백준 5526번 문제인 ダーツ (Darts)이다.
문제는 아래 링크를 확인하자.

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

네 개 이하의 다트로 얻을 수 있는 점수의 모든 합은 두 개 이하의 다트로 얻을 수 있는 점수의 합 두 개의 조합으로 항상 나타낼 수 있음을 관찰하자.

한편, 다트 하나를 사용하지 않은 것은 가상의 0점 영역에 다트를 던진 것으로 생각해도 결과가 같으므로, 이는 0점 영역을 추가한 후 다트를 항상 2개 사용하는 경우에 대한 문제로 바꿔 생각할 수 있다. 따라서, 위와 같이 변형된 상황에 대하여 두 개의 다트로 얻을 수 있는 점수 조합을 모두 구해둔 뒤, 이분탐색 또는 투포인터로 \(M\) 이하의 가능한 최댓값을 구해 문제를 해결할 수 있다.

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

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, idx;
int A[1001001];
int ans;

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> A[i];
	idx = N;
	for (int i = 0; i <= N; i++) {
		for (int j = i; j <= N ;j++) {
			A[++idx] = A[i] + A[j];
		}
	}
	N = idx + 1;
	sort(A, A + N);
	for (int L = 0, R = N - 1; L <= R; 1) {
		if (A[L] + A[R] > M) R--;
		else {
			ans = max(ans, A[L] + A[R]);
			L++;
		}
	}
	cout << ans;
}