[코드포스 - 1714C] Minimum Varied Number

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;

	int s;
	int list[9] = { 1,2,3,4,5,6,7,8,9 };
	vector<int> q(9,0);
	stack<int> stc;
	for (int i = 0; i < T; ++i)
	{
		cin >> s;
		for (int j = 9; 0 <= j; --j)
		{
			//원값이 클때
			if (s > j)
			{
				s -= j;
				stc.push(j);
			}
			//같을때
			else if (s == j)
			{
				stc.push(j);
				break;
			}
		}

		while (stc.empty() == false)
		{
			cout << stc.top();
			stc.pop();
		}
		cout << "\n";
	}

	return 0;
}

---

||사고 과정

먼저 규칙이 있나 확인했다.

input값이 1 ~ 45이기 때문에 분명 규칙이 있을거라고 생각했다.

 

10은 1 + 9,11은 2 + 9,12는 3 + 9 이런식으로 이루어지는걸 발견하고

뒤에서부터 숫자를 비교해 크면 빼고 작으면 다음, 같으면 종료 하기로 생각했고

 

또 생각해야할것은 어떻게 출력할까였는데 값을 뒤집어야 했다.

그래서 값을 뒤집기 편한 스택을 사용했다.

---

||사용 기법

• Greedy
• Stack

---

||나아 진것

• 규칙을 찾아보는것
• 자료구조를 이용한것

값 뒤집는 스택을 사용한건 편하게 잘 사용한것 같다.