[백준/BOJ] 백준 2494번 : 숫자 맞추기

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

2494번: 숫자 맞추기

위에서부터 숫자를 맞춰가며, cache[10000][10]에 [나사 인덱스][이전까지 left 상황]일때 원하는 상태로 만드는데 필요한 최소 회전 칸수를 저장하여 다이나믹 프로그래밍으로 문제를 해결했다.

 

코드

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

int n;
string start;
string dest;
int cache[10000][10]; //[나사 인덱스][left상황]
int result_count;
vector<int> result_history;

void Pre()
{
	for (int i = 0; i < 10000; i++)
		for (int j = 0; j < 10; j++)
			cache[i][j] = -1;
}

//index:나사 인덱스(0~n-1), before_left:이전까지 left 상황
int Solve(int index, int before_left)
{
	if (index == n)
		return 0;

	int& ret = cache[index][before_left];

	if (ret != -1)
		return ret;

	ret = 0;

	string here_number_s = "";
	here_number_s += start[index];
	int here_number = stoi(here_number_s);

	here_number += before_left;

	if (here_number >= 10)
		here_number -= 10;


	string there_number_s = "";
	there_number_s += dest[index];
	int there_number = stoi(there_number_s);

	int left_count;
	int right_count;

	if (here_number < there_number)
	{
		left_count = there_number - here_number;
		right_count = (10 + here_number) - there_number;
	}

	else if (here_number > there_number)
	{
		left_count = (10 + there_number) - here_number;
		right_count = here_number - there_number;
	}

	else
	{
		left_count = 0;
		right_count = 0;
	}

	int next_left = before_left + left_count;

	if (next_left >= 10)
		next_left -= 10;

	//왼쪽으로 돌렸을때와 오른쪽으로 돌렸을때 비교
	ret = min(Solve(index + 1, next_left) + left_count, Solve(index + 1, before_left) + right_count);

	return ret;
}

void SolveHistory(int index, int before_left)
{
	string here_number_s = "";
	here_number_s += start[index];
	int here_number = stoi(here_number_s);

	here_number += before_left;

	if (here_number >= 10)
		here_number -= 10;

	string there_number_s = "";
	there_number_s += dest[index];
	int there_number = stoi(there_number_s);

	int left_count;
	int right_count;

	if (here_number < there_number)
	{
		left_count = there_number - here_number;
		right_count = (10 + here_number) - there_number;
	}

	else if (here_number > there_number)
	{
		left_count = (10 + there_number) - here_number;
		right_count = here_number - there_number;
	}

	else
	{
		left_count = 0;
		right_count = 0;
	}

	int next_left = before_left + left_count;

	if (next_left >= 10)
		next_left -= 10;

	//왼쪽으로 돌렸을때와 오른쪽으로 돌렸을때 비교

	//지금 나사가 마지막일때
	if (index == n - 1)
	{
		//왼쪽으로 돌리는게 더 작거나 같을때
		if (left_count <= right_count)
		{
			result_history.push_back(left_count);
		}

		else
		{
			result_history.push_back(-right_count);
		}

		return; //종료
	}

	//왼쪽으로 돌리는게 더 작거나 같을때
	if (cache[index + 1][next_left] + left_count <= cache[index + 1][before_left] + right_count)
	{
		result_history.push_back(left_count);

		SolveHistory(index + 1, next_left);
	}

	else
	{
		result_history.push_back(-right_count);

		SolveHistory(index + 1, before_left);
	}
}

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

	Pre();

	cin >> n;
	cin >> start;
	cin >> dest;

	result_count = Solve(0, 0);

	SolveHistory(0, 0);

	cout << result_count << "\n";
	for (int i = 0; i < result_history.size(); i++)
	{
		cout << i + 1 << " " << result_history[i] << "\n";
	}

	return 0;
}