본문 바로가기

STUDY/Algorithm

[알고리즘] SW Expert Academy 10806. 수 만들기

문제 풀이 (사고의 흐름)


문제를 읽어보면, N개의 수 a,b,c....(>=2) 가 주어지고 이 수들을 곱한 값들을 더해서 K를 만드는 문제이다. 이때, K를 만들기위해 수를 더하는 회수를 최소로 해야한다. 처음에 문제를 풀기위해 "답을 구하기 위한 하나의 정확한 로직이 있을것이다" 라는 생각을 해버렸다. 계속 반복문을 돌려가서 정답을 찾아가는 것이 아닌, K에 a,b,c...를 곱하여 만들 수 있는 K보다 작거나 같은 수를 빼고... 남은값에서 이를 다시 반복하면 정답이 나올거라고 생각했다. 하지만 반례가 계속해서 나왔고 로직을 수정해보아도 새로운 반례가 나왔다.

 

그래서 다시 처음부터 생각을 고쳤다. "답을 한번에 구하는 완벽한 로직은 없다. 최선으로 계속 시도해서 답을 찾아보자". 수를 더하는 회수를 최소로 하고자하는 상태에서 계속 시도하는 반복문을 생각하자, 번뜩 우선순위 큐가 떠올랐다. 우선순위 큐로 더한 횟수가 작은 경우를 넣고 꺼내고 하다보면, 정답이 나오지 않을까?

 

또 정답을 수학적으로 한번 풀어서 생각해 보았다. K = a^3 * b^2 * c^1 + a^2 * b^1 + a^1 + 1과 같은 형태로 나오게된다. 여기서 재밌는 사실은 K를 다음과 같이 계속 나누면서 풀어쓸 수 있다는 것이다.

  • K = a^3 * b^2 * c^1 + a^2 * b^1 + a^1 + 1
  • K_1 (+1 제거, 즉 더하기 요소 하나 제거) = a^3 * b^2 * c^1 + a^2 * b^1 + a^1
  • K_1 나누기 a^1                                = a^2 * b^2 * c^1 + a^1 * b^1 + 1
  • K_2 (+1 제거)                                   = a^2 * b^2 * c^1 + a^1 * b^1
  • K_2 나누기 a^1 + b^1                       = a^1 * b^1 * c^1 + 1 
  • K_3 (+1 제거)                                   = a^1 * b^1 * c^1
  • K_3 나누기 a^1 * b^1 * c^1                = 1
  • K_4 (+1 제거)                                   = 0 = K로 가기위한 X의 시작값

시작값 K에서 a,b,c...로 만든 값을 빼고, 나누는 과정을 반복해서 0이 되게 만들고 빼는 횟수가 최소인것이 정답이다. 코드로 짜기위해 순서대로 생각해보면.

 

  1. 현재 시도회수 cnt와 0으로 가기위해 남은 값 left로 만들어진 obj 구조체를 만든다.
  2. 우선순위 큐인 pq에 obj(cnt = 0, left = K)를 넣는다
  3. pq에서 cnt가 최소인 min_obj을 꺼낸다.
  4. pq에 새로운 obj(cnt = min_obj.cnt + min_obj.left, left = 0)을 pq에 넣는다. (더이상 나눌 수 있는 a,b,c... 가 없어서 현재 수에서 계속 빼야하는 경우)
  5. N개의 a,b,c...를 돌며 새로운 obj(cnt = min_obj.cnt + min_obj.left % a,b,c..., left = min_obj.left / a,b,c...)를 pq에 넣는다
  6. 3번부터 다시 무한 반복, 다만 min_obj.left가 0이면 멈춘다
  7. 이때 min_obj.cnt가 정답이다.

 

 

정답코드


#include <iostream>
#include <queue>

using namespace std;

int N, K, Ans;
int Nums[11];

void Input() {
	int i;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &Nums[i]);
	}
	scanf("%d", &K);
}

void GetAns() {
	int i;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, K));
	while (pq.top().second) {
		pair<int, int> cur = pq.top();
		pq.pop();

		pq.push(make_pair(cur.first + cur.second, 0));
		for (i = 0; i < N; i++) {
			pq.push(make_pair(cur.first + cur.second % Nums[i], cur.second / Nums[i]));
		}
	}
	Ans = pq.top().first;
}

int main() {
	int t, t_i;
	scanf("%d", &t);
	for (t_i = 1; t_i <= t; t_i++) {
		Input();
		GetAns();
		printf("#%d %d\n", t_i, Ans);
	}
	return 0;
}

   

 

 

마무리


이 문제를 풀면서, 내가 알고리즘 문제를 풀때 가지는 잘못된 마음가짐에 대해 알게 되었다. 알고리즘 문제중에는 로직을따라 하나의 완벽한 정답으로 가는 경우도 존재하지만, 계속 시도하며 답을 찾아가는 경우도 존재한다. 최근들어 문제의 풀이법을 생각할 때, 풀이법에 대한 증명과 시간복잡도를 생각하려고하는 경향이 늘었다. 그 결과 확신이 들지 않는 풀이법을 생각하면 증명도 어렵고, 시간복잡도 계산도 잘 되지않아서 다른 방법을 찾아보려고 했었다. 하지만 이 문제는 풀고난 지금도 시간복잡도가 어떤지 계산이 안된다. 내가 부족하다는 사실을 인정하고 완벽하지 않은 풀이를 계속 시도해 보는것도 중요하다고 느꼈다.

반응형