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 헤더에 있다.