문제 개요
양의 정수로 이루어진 배열이 주어졌다고 가정해 보겠습니다. 배열에서 인접한 숫자들은 차례대로 실수(float) 나눗셈을 수행합니다. 예를 들어 [2,3,4]는 2 / 3 / 4로 계산됩니다.
여기에 우리는 원하는 위치에 원하는 만큼 괄호를 추가하여 연산 우선순위를 바꿀 수 있습니다. 목표는 결과값이 최대가 되도록 괄호를 배치하는 것이며, 그에 해당하는 수식을 문자열 형태로 반환해야 합니다. 단, 결과 수식에는 불필요한(중복된) 괄호가 포함되어서는 안 됩니다.
예를 들어 입력이 [1000,100,10,2]라면 정답은 "1000/(100/10/2)"입니다.
접근 방법: 왜 첫 번째 숫자만 분자로 남길까?
이 문제의 핵심 아이디어는 간단합니다. 모든 수가 양의 정수이므로, 나눗셈 결과를 최대화하려면 분자는 최대한 크게, 분모는 최대한 작게 만들면 됩니다.
x1 / x2 / x3 / ... / xn 형태에서 괄호를 어떻게 넣더라도 첫 번째 숫자 x1은 항상 분자 쪽에 위치하게 됩니다. 따라서 x1을 그대로 분자로 두고, 나머지 숫자들을 모두 괄호로 묶어 분모에 넣으면 다음과 같이 됩니다.
x1 / (x2 / x3 / ... / xn) = x1 × x3 × ... × xn / x2
분모에는 x2 하나만 남고 나머지 숫자들은 전부 곱셈으로 분자 쪽에 합쳐지므로, 이것이 가능한 모든 경우 중 가장 큰 값이 됩니다. 즉, 복잡한 동적 계획법 없이도 한 번의 순회(O(n))로 답을 구할 수 있는 그리디 방식의 문제입니다.
알고리즘 단계
- n := nums 배열의 크기
- n이 0이면 빈 문자열을 반환
- num := nums[0]을 문자열로 변환한 값
- n이 1이면 num을 그대로 반환
- n이 2이면 num + "/" + nums[1]을 반환 (괄호가 필요 없음)
- den := 빈 문자열
- i를 1부터 n-1까지 반복:
- den := den + nums[i]를 문자열로 변환한 값
- i가 n-1이 아니면 den := den + "/"
- num + "/(" + den + ")" 를 반환
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
if(n == 0) return "";
string num = to_string(nums[0]);
if(n == 1) return num;
if(n == 2) return num + "/" + to_string(nums[1]);
string den = "";
for(int i = 1; i < n; i++){
den += to_string(nums[i]);
if(i != n - 1) den += "/";
}
return num + "/" + "(" + den + ")";
}
};
main(){
vector<int> v = {1000,100,10,2};
Solution ob;
cout << (ob.optimalDivision(v));
}
입력
[1000,100,10,2]
출력
1000/(100/10/2)
마무리
이 문제는 겉보기에는 복잡한 괄호 조합 탐색처럼 보이지만, 양수 나눗셈의 성질(분자 극대화, 분모 극소화)을 파악하면 선형 시간에 해결됩니다. 특히 n이 2 이하일 때는 괄호가 필요하지 않으므로 이 경우를 별도로 처리하는 것이 구현상 중요한 포인트입니다.