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

문제

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

1082번: 방 번호

---

1. 첫 번째 풀이

사고 과정

방 번호의 크기에 가장 크게 영향을 끼치는 건 자릿수며, 그 다음이 (앞쪽부터) 숫자의 크기다.

 

단순하게는 자릿수를 최대한 늘린 뒤, 첫 자리부터 그리디하게 업그레이드 해나가면 될 것 같다.

1. 데이터 입력, 비용의 최솟값을 미리 구해둔다.
2. 각 번호의 비용에서 최소 비용을 뺀다.
   1. 이는 곧, 숫자를 업그레이드 비용하는 게 된다.
3. 가장 큰 번호부터 구매를 시도한다.
4. 만약 계산이 끝난 후, 첫 자리가 0이라면 자릿수를 1 낮춰 다시 시도한다.

 

코드

#include <iostream>
#include <vector>

int main() {
	// 입력
	int n;
	std::cin >> n;

	int min_index = 0;
	std::vector<int> cost(n);
	std::vector<int> upgrade(n);

	for (int i = 0; i < n; i++) {
		std::cin >> cost[i];
		// 같은 값이면 큰 수가 좋다.
		if (cost[i] <= cost[min_index]) { min_index = i; }
	}

	for (int i = 0; i < n; i++) {
		upgrade[i] = cost[i] - cost[min_index];
	}

	int m;
	std::cin >> m;

	// 계산
	int place = m / cost[min_index];	// 자리 개수
	std::vector<int> num;

	do {
		num.assign(place, min_index);

		int balance = m - place * cost[min_index];

		// 모든 자릿수에 대해 반복 (i: 자릿수)
		for (int i = 0; i < place; i++) {
			// min_index보다 큰 수에 대해서만 비교 (j: 숫자, 0 ~ 9)
			for (int j = n - 1; j > min_index; j--) {
				if (balance - upgrade[j] >= 0) {
					balance -= upgrade[j];
					num[i] = j;
					break;	// 다음 자릿수로 이동
				}
			}

			// 잔액이 0원이 되면 바로 종료
			if (balance == 0) { break; }
		}

		// 한 자리 숫자가 아닌데 첫 자리가 0이라면, 자릿수를 1 줄이고 반복한다.
	} while (place-- > 1 && num[0] == 0);

	// 출력
	for (auto& i : num) {
		std::cout << i;
	}
}

 

결과

 

그리디한 방법으로 풀이에 성공했다.

그럼 분류가 왜 DP였을까? DP로 하면 더 빠른 결과가 나올까?

 

풀이 시간: 1시간

---

개선

사고 과정

가장 먼저 떠오르는 방법은, M(주어진 돈)을 인덱스로 하는 DP.

DP의 핵심은 이미 구해둔 값들을 활용해 새 값을 구하는 것인데, M을 기준으로 두면 불가능하다.

 

3원일 때 방 번호와 5원일 때 방 번호를 곱해서 15원일 때가 나오지 않고, 더해서 8원일 때가 나오지 않는다.

 

N을 인덱스로 둘 순 없다. 얜 애초에 정보니까.

 

그렇다면 자릿수는 어떨까? 자리의 개수를 인덱스로 두면?

 

간단하게 5자리 수를 살펴보자.

5자리 방 번호를 만들려면 4자리 수에 1자리를 더하거나, 3자리 수에 2자리를 더하거나, 2자리 수에 3자리를 더하거나, 1자리 수에 4자리를 더해야 한다.

 

2자리 수와 3자리 수를 더하면 5자리 수가 되겠지만, 문제는 둘 다 M을 기준으로 구한 번호라는 것. 둘을 붙여서 M이 넘으면 의미 없어진다.

 

그럼 4자리 수에 1자리를 더하는 게 가장 효과적이다. 하지만 이때, 돈이 부족해 아무 숫자도 살 수 없는 경우가 있다.

그 경우엔 3자리 수로 돌아가, 2개의 수를 사야 한다. 이땐 그리디하게 앞 숫자부터 사면 된다.

 

근데 이거, 결국 첫번째 방법의 다운그레이드가 아닐까? 결국 DP를 채울 때마다 그리디하게 계산을 돌려야 한다. 별 의미가 없을 것 같다.

---

가장 효율적인 코드

내 코드와 비교

https://www.acmicpc.net/source/29665772

rhdqor213님의 코드. 비록 변수명 때문에 알아보긴 힘들었지만, 그래도 분석할 수 있었다. 차이점을 분석해보면

 

1. 0을 제외한 가장 저렴한 값을 함께 캐싱해뒀다. 이를 통해 첫 자리를 0이 아니게 고정했다.
   1. 그 덕에 자릿수가 줄어드는 경우가 사라졌고, 한 번의 반복문이면 충분해졌다.
   2. 0을 제외할 때 && i로 비교한 부분도 대단했다.
2. 나는 num(저 분의 코드에선 b)의 0번 자리부터 값을 바꿨고, 이 분은 끝 자리부터 값을 바꿨다.
3. 나는 n - 1부터 min_index보다 큰 값까지, 감소하며 비교했고, 이 분은 min_index(이 분은 e) + 1부터 n - 1까지 증가하며 비교했다.
   1. 이 부분은 내 코드가 더 나은 것 같다. 나는 값이 바뀌는 순간 바로 탈출하는 반면, 이 분의 코드는 항상 끝까지 검사해야 한다.

큰 줄기는 이 정도다. 배워갈 부분도 있었고, 내가 더 나은(듯한) 부분도 있었다.

---

강평

DP 문제지만 그리디로 풀었고, 다른 분의 코드를 보며 배워갈 수 있었던 문제.

...아직도 왜 분류가 DP인지 모르겠다.