[백준] 12852번 1로 만들기 2

문제: 12852번: 1로 만들기 2

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	// second 에 이전에 지나온 수 저장
	vector<pair<int, int>> table(n+1); // 0번 인덱스는 안 써~

	// 1 은 연산 횟수가 0 이니까 그냥 2부터 시작하기
	for (int i = 2; i < n + 1; i++) {
		int threeNum = INT_MAX;
		int twoNum = INT_MAX;
		int oneNum = INT_MAX;

		if (i % 3 == 0) {
			threeNum = table[i / 3].first + 1;
		}
		if (i % 2 == 0) {
			twoNum = table[i / 2].first + 1;
		}
		oneNum = table[i - 1].first + 1;

		int minNum = min({ threeNum, twoNum, oneNum }); // 최솟값 넣어주깅~
		table[i].first = minNum;

		// 이전값 저장
		if (minNum == threeNum) {
			table[i] = make_pair(minNum, i/3);
		}
		if (minNum == twoNum) {
			table[i] = make_pair(minNum, i / 2);
		}
		if (minNum == oneNum) {
			table[i] = make_pair(minNum, i - 1);
		}
	}

	queue<pair<int, int>> nums;
	nums.push(table[n]);
	cout << table[n].first << "\n"; // 최솟값 출력
	cout << n << " ";
	while (!nums.empty()) {
		pair<int, int> cur = nums.front();
		nums.pop();

		int prev = cur.second;
		if (prev != 0) {
			cout << cur.second << " ";
			nums.push(table[prev]); // nums 에 넣기
		}
		else if (prev == 0) {
			break; // 종료~
		}
	}

	return 0;
}

 

주어진 수 n 이 1 로 가는 방법의 최솟값과 과정을 출력해주면 된다.

 

과정을 출력해주기 위해 vector 에 최솟값만 저장하는 것이 아닌 이전 값도 같이 저장해준다. 이렇게 하면 큐를 이용해서 n 부터 1까지 접근할 수 있다.

 

큐를 돌면서 출력해주면 그게 바로 n 이 1로 가는 과정을 출력하는 것이다 !_!