세 개의 숫자 A, B, C가 주어졌다고 가정해 봅시다. 다음과 같은 게임을 생각할 수 있습니다. 1부터 9까지의 숫자가 각각 적혀 있는 '숫자 패널' 세 개와 '+' 기호가 적혀 있는 '연산자 패널' 한 개가 존재합니다. 플레이어는 이 네 개의 패널을 왼쪽에서 오른쪽으로 배열하여 X+Y 형태의 수식을 완성해야 합니다.
이때 플레이어가 받게 되는 허용 금액은 완성된 수식의 계산 결과값과 같습니다. 우리의 목표는 가능한 최대 허용 금액을 구하는 것입니다.
예를 들어 입력이 A = 1, B = 5, C = 2라고 한다면 출력은 53이 됩니다. 패널을 52+1로 배치했을 때 얻을 수 있는 값이 가장 크기 때문입니다.
문제 해결 접근 방법
이 문제의 핵심은 두 자리 숫자를 만들 때 가장 큰 숫자를 십의 자리에 배치하는 것입니다. 십의 자리 숫자는 결과값에 10배의 가중치로 영향을 미치므로, 가장 큰 숫자를 십의 자리에 놓고 나머지 두 숫자를 더하는 수로 사용하면 항상 최대값을 얻을 수 있습니다.
구체적인 해결 단계는 다음과 같습니다.
A, B, C를 포함하는 배열 V를 정의한다 배열 V를 오름차순으로 정렬한다 ans := (V[2] * 10) + V[1] + V[0] ans를 반환한다
정렬 후 V[2]는 세 숫자 중 가장 큰 값이 되며, 이 값을 십의 자리에 배치하고 나머지 두 숫자 V[1], V[0]을 더하면 최대 허용 금액이 계산됩니다.
예제 코드
더 나은 이해를 위해 다음 C++ 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int A, int B, int C){
vector<int> V = { A, B, C };
sort(V.begin(), V.end());
int ans = (V[2] * 10) + V[1] + V[0];
return ans;
}
int main(){
int A = 1;
int B = 5;
int C = 2;
cout << solve(A, B, C) << endl;
}입력
1, 5, 2
출력
53
복잡도 분석
이 알고리즘의 시간 복잡도는 세 원소를 정렬하는 데 드는 비용으로 O(1)입니다. 원소가 고정된 3개뿐이므로 사실상 상수 시간 내에 처리되며, 추가 메모리 사용 없이 효율적으로 동작합니다.