[백준 9440] 숫자 더하기

백준 9440번 : 숫자 더하기

www.acmicpc.net/problem/9440

9440번: 숫자 더하기

 

---

/* 문제 설명 */

N(2 ≤ N ≤ 14)개의 0~9 사이의 숫자가 주어질 때, 숫자들을 조합하여 우선 두 개의 숫자를 만든다.

만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수를 구하시오.

 

/* 해결 방안 */

두 숫자를 더했을 때, 최소가 되려면 어떻게 해야할까?

숫자의 앞에서 부터 뒤를 봤을 때, 큰 숫자를 어디로 배치해야할지 떠올려보자.

큰 숫자는 무조건 뒤에다가 배치해야 최소를 만들 수 있다.

(ex. 321 vs 123)

 

따라서 두 숫자를 더했을 때, 최소로 만들기 위해서는 두 숫자가 나올 수 있는 조합 중에서 가장 작아야 된다.

그러므로 오름차순으로 정렬한 후, 작은 수 부터 번갈아가며 두 숫자에 넣어주자.

 

한가지 주의할 점으로는 0을 처리해줘야 한다는 점이다.

 

1) 0이 하나일 때, v[0]와 v[2]를 바꿔준다.

 

만들어지는 두 숫자 모두 첫 번째 자리가 0이면 안되기 때문이다.

또한 0이 주어질 경우에는 무조건 최소 2개 이상의 0이 아닌 수가 주어지므로,

0이 하나일 때면, 언제나 v[0]과 v[2]를 바꿔줄 수 있다.

   ex. 0 1 2 3 같은 경우에는 0을 2와 바꿔주어 2 1 0 3이 되어 20+13=33이 된다.

 

 

2) 0이 두 개 이상일 때는 v[0]과 v[zero], v[1]과 v[zero+1]를 바꿔준다.

 

zero는 현재 배열에 있는 0의 개수를 의미한다. 

즉, v[zero]는 zero개 만큼의 0을 지나 처음으로 만나는 자연수를 뜻하게 되는 것이다.

0 0 0 0 4 5 7 8 과 같은 경우에 v[0]과 v[4], v[1]과 v[5] 이렇게 바꿔주기 위함이다.

 

/* 구현 과정 */

1. N개의 숫자에 대해 배열에 입력을 받고, 정렬을 해준다.

2. 0이 맨 앞에있는 경우를 처리해준다. (총 두 가지 경우)

3. 배열의 앞에서 부터 번갈아가며 넣어주어 두 숫자를 만든다.

(이 때, 구현을 쉽게 하기 위해서 값을 문자열로 변환한다.)

4. 만들어진 두 숫자(string)를 int로 고쳐주어 둘의 합을 구한다.

 

/* 소스 코드 */

1) 그리디

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define mod 10007
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<int, pi>pii;

string str;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	while (1) {
		int n, zero = 0; cin >> n;
		if (n == 0) break;

		vector<int>v;
		for (int i = 0; i < n; i++)
		{
			int a; cin >> a;
			if (a == 0) zero++; //0이 맨 앞에 있는 경우 따로 처리를 해야한다.
			v.push_back(a);
		}
        
		sort(v.begin(), v.end());

        //0이 하나인 경우에는 0 1 2 3 → 2 1 0 3으로 교체하여,
        //만들어지는 두 개의 숫자에 대해 어떠한 것도 첫 시작이 0이 아니도록 한다.
		if (zero == 1) swap(v[0], v[2]);
        
        //0이 두 개 이상인 경우에는, 0 0 0 1 2 3 이므로, zero개 이후에 있는 숫자와 바꾼다.
		if (zero >= 2) {
			swap(v[0], v[zero]);
			swap(v[1], v[zero + 1]);
		}

		string l = "", r = "";
		for (int i = 0; i < v.size(); i++)
		{
            //0을 추가하는 경우에도 쉽게 처리하도록 문자열로 고쳐준다
			string now = to_string(v[i]);
			if (i % 2 == 0) l += now;
			else r += now;
		}
        //문자열을 숫자로 변환하여 답을 구한다.
		cout << stoi(l) + stoi(r) << "\n";
	}
}

 

2) 완전탐색

아주 먼 옛날 이렇게 풀었더라..

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
typedef pair<int, int>pi;
typedef pair<pair<int, int>, int>pii;
typedef long long ll;

int n, N, ans = INF;
vector<int>arr;
vector<bool>chk;

void dfs(int x, int k) {
	if (k == N) {
		string A, B;
		for (int i = 0; i < n; i++)
		{
			if (chk[i]) A.push_back(arr[i]+'0');
			else B.push_back(arr[i]+'0');
		}
		sort(A.begin(), A.end());
		int flag1 = 0;
		for (flag1 = 0; flag1 < A.size(); flag1++) if (A[flag1] != '0') break;
		if (flag1 == (int)A.size()) return;
		for (int i = flag1; i > 0; i--) swap(A[i], A[i - 1]);

		sort(B.begin(), B.end());
		int flag2 = 0;
		for (flag2 = 0; flag2 < B.size(); flag2++) if (B[flag2] != '0') break;
		if (flag2 == (int)B.size()) return;
		for (int i = flag2; i > 0; i--) swap(B[i], B[i - 1]);

		int a = stoi(A);
		int b = stoi(B);
		ans = min(ans, a + b);
		return;
	}

	for (int i = x + 1; i < n; i++)
	{
		if (chk[i]) continue;
		chk[i] = 1;
		dfs(i, k + 1);
		chk[i] = 0;
	}
}
int main() {
	while (1) {
		scanf("%d", &n);
		if (n == 0) break;

		N = n / 2;
		arr.resize(n); chk.resize(n);
		for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
		dfs(0, 0);

		printf("%d\n", ans);
		arr.clear(); chk.clear();
		ans = INF;
	}
}

 

/* 얻어갈 점 */

1. 그리디 문제를 풀 때는 최대한 단순하게 생각하자!

 

 

 

---