[백준]1082번 방 번호 - C/C++

https://www.acmicpc.net/problem/1082

1082번: 방 번호

문제

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해야 한다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. M원을 모두 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.

출력

첫째 줄에 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

---

우선 최대한 숫자의 자릿수를 크게 만드는 것이 큰 숫자를 만들 수 있기 때문에 가장 싼 숫자로 자릿수를 최대한 늘린다음에 남은 돈으로 큰 자릿수부터 바꾸어 나가는 방법을 활용했다. 이때 0은 맨 앞자리에 올 수 없기 때문에 가장 싼 숫자가 0이라면 그 다음으로 싼 숫자를 구해주었다.

#include <iostream>

using namespace std;

int N, M;
int cost[10];
int ans[51];

void solve() {
	int h_min = 1, r_min = 0, idx = 1;
	for (int i = 0; i < N; i++) {
		if (cost[i] <= cost[r_min])
			r_min = i;
	}
	if (r_min == 0) {
		for (int i = 1; i < N; i++) {
			if (cost[i] <= cost[h_min])
				h_min = i;
		}
	}
	else h_min = r_min;

	if (M < cost[h_min] || N == 1) {
		cout << "0";
		return;
	}
	ans[0] = h_min;
	M -= cost[h_min];
	while (1) {
		if (M - cost[r_min] < 0)
			break;
		M -= cost[r_min];
		ans[idx++] = r_min;
	}
	for (int i = N - 1; i > h_min; i--) {
		if (M - (cost[i] - cost[h_min]) >= 0) {
			ans[0] = i;
			M -= (cost[i] - cost[h_min]);
			break;
		}
	}
	int p = 1, reduce = cost[r_min];
	for (int i = 0; i < N; i++) {
		cost[i] = cost[i] - reduce;
	}
	while (1) {
		int tmp = ans[p];
		for (int i = N - 1; i >= 0; i--) {
			if (M - cost[i] >= 0) {
				ans[p] = i;
				M -= cost[i];
				break;
			}
		}
		if (tmp == ans[p]) break;
		p++;
	}


	for (int i = 0; i < idx; i++) {
		cout << ans[i];
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> cost[i];
	}
	cin >> M;
	solve();
}

---

하지만 틀렸다! 구글링을 해도 맞는 방법인 것 같은데 어느 부분에서 디테일이 부족한지 아직 파악하지 못했다. 조금 더 고민을 해봐야겠다! 오늘은 SWEA 문제도 잘 안풀리고 백준 문제도 잘 안풀리는 하루여서 자신감이 조금 떨어졌다. 몇 주전에도 이런 날이 있었는데 또 금방 잘 풀리는 날이 왔다! 내일은 잘 풀리는 날이 왔으면 좋겠다.

 

이틀뒤에 코드를 다시 보자마자 틀린부분을 알게되었다. 나머지 자릿수를 구할때 M-cost[i] >=0 에는 등호가 있었는데 첫째 자릿수를 제일 큰 숫자로 바꾸는 부분에는 등호가 없어서 등호를 넣으니 통과했다. 저번에 코드를 몇번이나 확인했는데 못봤던게 신기하다. 다른 사람 코드랑 비교할때는 뭔가 비교에 초점을 둬서인지 이런 작은 코드들이 잘 안보이는 것 같다.