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

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

1082번: 방 번호

---

문제 설명

 

---

접근 방법

그리디 알고리즘으로 문제를 해결하였다.

우선, 자릿수가 길 수록 큰 수이기 때문에, 내가 만들 수 있는 가장 긴 자릿수를 구한다.

이는 가격이 가장 싼 번호

(단, 맨 처음에는 0이 되면 안된다.따라서 0을 제외한 가장 작은 수 A, 0을 포함한 가장 작은수 B를 각각 구해야 한다.)

로만 방을 구성했을 경우을 배열에 집어넣는다.

이는 ABBBBBBB... 이런한 꼴이 될 것이다.

그 후에 맨 첫 자리부터 가능한 큰 수로 바꾸는 연산을 진행시킨다.

A보다 큰 C라는 수를 예산안에 넣을 수 있다면 가장 큰 번호는 CBBBBBB...이러한 꼴이 된다.

마찬가지로 다음 자릿수또한 똑같은 연산을 한 후, 마지막 자리까지 반복해준다.

이러한 과정을 통해 가장 큰 방번호를 구할 수 있다.

---

코드

#include <iostream>
#include<string>
#include<queue>
using namespace std;
int price[10];
int n, m;
int r[51];
int minPrice=50;
int minIndex;
int minPrice2 = 50;
int minIndex2;
int idx;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> price[i];
		if (i > 0&& price[i] <= minPrice) {
			minPrice = price[i];
			minIndex = i;
		}
		if(price[i] <= minPrice2) {
			minPrice2 = price[i];
			minIndex2 = i;
		}
	}
	cin >> m;
	if (m < minPrice) {
		cout << '0';
		return 0;
	}
	r[0] = minIndex;
	m -= minPrice;
	idx++;
	while (m >= minPrice2) {
		m -= minPrice2;
		r[idx] = minIndex2;
		idx++;
	}
	for (int i = 0; i < idx;i++) {
		for (int j = n-1; j >r[i]; j--) {				
			if (m + price[r[i]]-price[j]>=0) {		
				m += price[r[i]];
				m -= price[j];
				r[i] = j;
				break;
			}
		}
	}
	for (int i = 0; i < idx; i++) { cout << r[i]; }

---

유독 그리디문제를 풀 때 해매는 것 같다.