SWEA 4254 - 가장 큰 수 만들기

링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3lS6aF-MDFAWJ

문제

별표(*) 또는 0~9 숫자가 3개 적힌 카드가 N개 있을 때, 숫자끼리 연결되게 이어 붙여서 그 때의 모든 숫자의 합이 가장 큰 것을 구하는 문제이다.

여기서 별표(*)는 숫자를 연결하지 못하도록 만드는 구분자라고 생각하면 된다.

단순해보이지만 케이스를 제대로 생각못해서 여러번 시도 끝에 맞췄다.

풀이는 브루트 포스(Brute force)이다.

먼저 숫자 카드는 아래처럼 6가지의 케이스가 있을 것이다.

편의상 (a) + (b) = 12312* 와 같이 적겠다.

숫자로만 이루어진 (a)는 어디에든 붙을 수 있으니, 그냥 무조건 더해도 된다.

어느 한쪽에만 붙는 (b), (c), (d) 까지 합치면, 최종 형태는 ((d) or (c)) + (a) + ((b) or (c)) 중에 합이 가장 큰 것을 찾으면 된다.

여기서 (c)가 양 쪽으로 중복되어 선택되지 않도록 하는 것에 조심해야한다.

보이지 않는 케이스로, 모든 숫자 카드가 붙지 못하는 경우가 있다. (e) 혹은 (c)만 계속 입력되는 것인데, 등장하는 가장 큰 숫자(하나)도 확인하면 된다.

코드

이 문제에서는 라이브러리 사용이 금지된 것 같다. 그래서 코드가 좀 깔끔해지지 못했다.

재밌는 점은, GNU gcc에서 std::max 함수는 iostream 헤더에 있다.

	#include <iostream>
	#include <algorithm>
	using namespace std;
	typedef long long lld;
	int sum(char *s) {
	int r = 0;
	for (int i = 0; s[i]; ++i)
	if (s[i] != '*') r += s[i] - '0';
	return r;
	}
	int solve() {
	int n, postmax = 0, premax = 0;
	int mid[1001][2], mi = 0;
	cin >> n;
	int midsum = 0, solo = 0;
	for (int i = 0; i < n; ++i) {
	char t[4];
	cin >> t;
	if (t[0] == '*' && t[1] == '*' && t[2] == '*') continue;
	if (t[0] != '*' && t[1] != '*' && t[2] != '*') { // case (a)
	midsum += sum(t);
	}
	else if (t[0] != '*' && t[2] != '*') { // case (c)
	mid[mi][0] = t[0] - '0';
	mid[mi++][1] = t[2] - '0';
	solo = max(solo, max(t[0], t[2]) - '0');
	}
	else if (t[2] != '*') { // case (d)
	premax = max(premax, sum(t));
	}
	else if (t[0] != '*') { // case (b)
	postmax = max(postmax, sum(t));
	}
	else { // case (e)
	solo = max(solo, t[1] - '0');
	}
	}
	int ans = premax + midsum + postmax;
	for (int i = 0; i < mi; ++i) {
	ans = max(ans, mid[i][1] + midsum + postmax);
	ans = max(ans, premax + midsum + mid[i][0]);
	for (int j = 0; j < mi; ++j) {
	if (i == j) continue;
	ans = max(ans, mid[i][1] + midsum + mid[j][0]);
	}
	}
	return max(solo, ans);
	}
	int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
	cout << '#' << tc << ' ' << solve() << '\n';
	}
	return 0;
	}

view raw swea-4254.cpp hosted with ❤ by GitHub