C++ / 12852 / 1로 만들기 2 ( 백트래킹 )

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

문제 요약

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 입니다.

1. X가 3으로 나누어 떨어지면, 3으로 나눕니다.
2. X가 2로 나누어 떨어지면, 2로 나눕니다.
3. 1을 뺍니다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최솟값을 출력해야 합니다.

문제 풀이

1. 정수를 입력받습니다. 

2. dfs 탐색을 하는데, 현재  개수가 저장해둔 개수보다 커지면 탐색을 리턴합니다. ( 첫 회차엔 1e9가 저장 되어 있음 )  

3. 현재 숫자를 임시 배열에 저장하고 재귀 호출합니다. ( 3으로 나누어 떨어지면 3으로 나눠서, 2로도 나누어 떨어지며 2로 나눠서, 마지막으로 -1 )

4. 현재 만들어진 숫자가 1이면 현재 개수가 저장해둔 개수보다 작으면 저장하고 현재 숫자를 임시 배열에 추가 한 후 ( 아래 탐색 시작할때 현재 숫자를 추가하게 하였기 때문에 )

정답 배열을 임시 배열로 초기화 하여 리턴합니다.

5. 그렇게 마저  탐색하면서 가장 적은 개수와 그 정수들을 갱신합니다.

6. 탐색이 종료 되면 저장해 두었던 개수를 출력하고 정답 배열을 출력합니다.

주의할 점

아래 코드는 처음에 풀었던 코드입니다.

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


long long int n, ret = 1e9;
vector<long long int> v;
vector<long long int> ans;
vector<bool>visit;

void dfs(long long  int x, long long int cnt)
{

	v.push_back(x);
	if (x == n)
	{
		if (cnt < ret)
		{
			ans.clear();
			ret = min(cnt, ret);
			ans = v;

		}
		return;
	}
	for (int i : {x * 3, x * 2, x + 1})
	{
		if (i > n)
		{
			continue;
		}

		if (!visit[i])
		{
			visit[i] = true;
			dfs(i, cnt + 1);
			visit[i] = false;
			v.pop_back();
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	visit.resize(n + 1);
	dfs(1, 0);
	cout << ret << "\n";
	for (int i = ans.size() - 1; i >= 0; i--)
	{
		cout << ans[i] << " ";
	}
	return 0;
}

1부터 n까지 탐색하는데 그 과정에서 반복문을 사용하였으나 시간초과가 발생하였습니다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;


long long int n, ret = 1e9;
vector<long long int> v;
vector<long long int> ans;
vector<bool>visit;

void dfs(long long  int x, long long int cnt)
{
	if (cnt > ret)
	{
		return;
	}
	if (x == 1)
	{
		if (cnt < ret)
		{
			ret = cnt;
			// 현재 숫자 추가
			v.push_back(x);
			// 정답 경우의 수 저장
			ans = v;
			// 현재 숫자 삭제
			v.pop_back();

		}
		return;
	}
	// 현재 숫자 추가
	v.push_back(x);
	if (x % 3 == 0)
	{
		dfs(x / 3, cnt + 1);
	}	
	if (x % 2 == 0)
	{
		dfs(x / 2, cnt + 1);
	}	
	dfs(x - 1, cnt + 1);
	// 현재 숫자 삭제
	v.pop_back();


}

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

	cin >> n;
	visit.resize(n + 1);
	dfs(n, 0);

	cout << ret << "\n";
	for (int i : ans)
	{
		cout << i << " ";
	}
	return 0;
}

반응형

예제 1

2

결과 1

예제 2

10

결과 2