본문 바로가기

Programming Problems/Arrays

연속된 숫자 배열이 주어졌을 때, 숫자로 만든 합의 최소는?

ex ) 1 2 7 8 9 의 최소합은 129+78 (순서 바꾸기 가능)


나이브 솔루션 : 그냥 두 집합으로 쪼갠 후에 합을 구해 최소를 찾는다 > 각 합을 만드는 시간 O(N), 갯수 : 2^N

O(N2^N) 솔루션


성질을 더 이용해 보자. DP 하기에는 성질을 너무 많이 사용하고 앞의 값을 재활용하기 어렵다(?) 아닌데. 앞의 최소합이 있으면 새로운 원소가 들어오는 경우 둘 중 더 작은 값으로 가야하지 않나? 엌 greedy 방법이 여기잉네

된다. greedy. 나머지가 이미 최소값인 조합으로 구성되어 있기 때문에, 새로운 숫자를 더 작은쪽에 붙이면 된다.


알고리즘

뒤에서부터 숫자를 만들어 나간다. 그때그때 대소비교를 O(1)에 할 수 있도록 알고리즘을 짜면

작은 쪽의 맨 앞에 숫자를 append 하면 된다. 그리고 string은 뒤집어서 만들어 나가다가 마지막에 뒤집는게 좋겠다.


string findminsum(string s){

if(s.size()==0) return s;

string t1 = "";

string t2 = s[s.size()-1];

bool add2 = false;

for(int i = s.size()-2; i>= 0 ; i--){

if(add2) t2.push_back(s[i]);

else t1.push_back(s[i]);

// update comparing

if(t1.size()>t2.size()) add2 = true;

else if(t1.size()<t2.size()) add2 = false;

else {

if(t1.back()>t2.back()) add2 = true;

else add2 = false;

}

}

return add(t1,t2);

}


string add(string t1, string t2){

int carry = 0;

string ret = "";

int curr = 0;

while(t1.size()<curr && t2.size()<curr){

int tot = t1[curr]+t2[curr]-2*'0';

if(tot>=10) {

tot -= 10;

carry = 1;

}else{

carry = 0;

}

ret.push_back(tot);

curr++;

}

while(t1.size()<curr){

ret.push_back(t1[curr]);

curr++;

}

while(t2.size()<curr){

ret.push_back(t2[curr]);

curr++;

}

reverse(ret.begin(),ret.end());

return ret;

}


시간 복잡도는 N 루프를 돌면서 그 안에서 1 연산을 하므로 O(1)이다. 리턴 어레이를 고려하면 space complexity는 O(N) 이다.


성질을 이용하는거 생각은 잠깐 후에.. 아마도 크기가 무조건 절반 사이즈여야 최소일 테니까, 빈 두 어레이를 만들어서 최소합으로 배치하는 알고리즘을 짤 수 있을 것 같은데 그리디로 해가 나왔으므로 필요하면 더 생각해 보자.