[백준/BOJ] 1082. 방번호 [Gold 3]

1082. 방번호

문제출처 : https://www.acmicpc.net/problem/1082

참고블로그 : https://sdy-study.tistory.com/226

참고글 : https://www.acmicpc.net/board/view/47793

code)

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
	int N, M;
	cin >> N;
	vector<int> arr(N);
	vector<int>result;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	cin >> M;

	int first = 51, second = 51;
	int first_index = 0, second_index = 0;

	for (int i = 0; i < N; i++)
	{
		if (arr[i] < first)
		{
			first = arr[i];
			first_index = i;
		}
	}
	for (int i =1; i < N; i++)
	{
		if (arr[i] < second)
		{
			second = arr[i];
			second_index = i;
		}
	}

	if (M < second)
	{
		cout << 0;
		return 0;
	}

	M -= second;
	result.push_back(second_index);
	while (M >= first)
	{
		result.push_back(first_index);
		M -= first;
	}

	int index;

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

	for (int i = 0; i < result.size(); i++)
		cout << result[i];

	return 0;
}

컨디션이 안좋아서 그런가... 일주일동안 고민했는데도 못풀겠다.
사실 지금도 보면은 어떻게 풀었는지 알겠는데 안보고 다시해보라하면 못할것같다.

제일 앞자리 숫자는 1~N까지 숫자중 가장 싼값의 숫자를 넣고
그다음 숫자부터는 0~N까지 숫자중 가장 싼값을 넣고나서,
나머지 남는 돈으로 첫째자리부터 더 높은 숫자로 바꿀 수 있는지 확인하는 절차를 거치면 되는데,

다이나믹 프로그래밍 부분 구현을 어떻게 해야할지 모르겠다 너무 어려워ㅠㅠㅠ
그래서 다이나믹프로그래밍 쉬운문제부터 차근차근 어떻게 풀어야 하는지 감을 익혀야 겠다.