백준 1082 c++ "방 번호" -PlusUltraCode-

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

 

[필자 사고]

첫째자리 오는 수는 0이 올수 없기때문에 이 부분 주의해야 한다.

먼저 필자는 가장 작은 값어치를 찾아야 했다.

실제 인덱스가 0인 경우와 아닌 경우 둘다 찾았다.

 

그다음 resultArr배열에 첫재짜리만 따로 넣어준뒤 반복문을 이용하여 최소비용으로 만들 수 있는 

최대 자릿수를 알아냈다. 

그다음 전체 반복문을 조회하여 해당 인덱스보다 큰 인덱스인데 값어치가 아직 여유있는 경우들을 하나씩 바꿔나갔다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 단계

• 먼저 사용할 수 있는 숫자의 개수를 입력받고, 각 숫자를 사용하기 위한 비용을 벡터에 저장합니다.
• 그리고 사용할 수 있는 총 금액을 입력받습니다.

2. 가장 저렴한 숫자 두 개를 찾음

• 모든 숫자 중 가장 비용이 적은 숫자를 찾습니다. 이건 반복적으로 사용할 숫자를 결정할 때 기준이 됩니다.
• 또한, 가장 앞자리에 오는 숫자는 0이면 안 되므로, 0번 숫자를 제외하고 가장 저렴한 숫자도 따로 찾습니다.

3. 첫 자릿수 결정

• 가장 앞자리에 올 수 있는 가장 저렴한 숫자가 현재 가진 돈으로 살 수 없다면, 어떤 숫자도 만들 수 없기 때문에 프로그램은 0을 출력하고 종료합니다.
• 만약 살 수 있다면, 그 숫자를 첫 자리에 넣고 해당 비용만큼 총 금액에서 차감합니다.

4. 가능한 한 많은 숫자 구매

• 그 다음으로는 가장 저렴한 숫자를 이용해 남은 돈으로 최대한 많은 숫자를 구매하여 숫자의 전체 길이를 최대화합니다.

5. 숫자 업그레이드

• 이제 만들어진 각 자릿수 숫자를 더 큰 숫자로 바꿀 수 있는지 하나씩 확인합니다.
• 각 자리를 오른쪽에서부터가 아니라 왼쪽부터, 그리고 가능한 숫자 중 가장 큰 값부터 시도합니다.
• 만약 현재 자리에 들어간 숫자를 더 큰 숫자로 바꾸는 데 드는 추가 비용이 남은 금액 내라면, 해당 자릿값을 더 큰 숫자로 바꾸고, 그만큼 금액을 다시 차감합니다.
• 이 과정을 모든 자리수에 대해 반복하여 숫자를 최대한 크게 만듭니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;



int N, M;
vector<int> arr;
vector<int> arr2;
vector<int> resultArr;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	cin >> M;
}

void Game_Start() {
	int firstValue = INF; int secondValue = INF;
	int firstIdx, secondIdx;

	for (int i = 0; i < arr.size(); i++) {
		if (firstValue > arr[i]) {
			firstValue = arr[i];
			firstIdx = i;
		}

		if (i != 0 && secondValue > arr[i]) {
			secondValue = arr[i];
			secondIdx = i;
		}
	}

	if (secondValue > M) {
		cout << '0';
		return;
	}
	
	M -= secondValue;
	resultArr.push_back(secondIdx);

	while (M > 0) {
		int diff = M - firstValue;
		if (diff < 0)break;
		resultArr.push_back(firstIdx);
		M -= firstValue;
	}


	for (int i = 0; i < resultArr.size(); i++) {
		
		for (int j = N - 1; j >= 0; j--) {
			int diff = arr[j] - arr[resultArr[i]];
			if (diff <= M) {
				resultArr[i] = j;
				M -= diff;
				break;
			}
		}
	}

	for (int i = 0; i < resultArr.size(); i++) {
		cout << resultArr[i];
	}

	

}

int main(void) {
	Input();
	Game_Start();
}