[백준] C++ 12852(1로 만들기 2)

문제 해결 방법

1. 1부터 N까지 연산의 최솟값을 구한다.(DP배열)

2.  N을 1로 만드는 방법을 위 값을 기반으로 찾는다.

 

2의 연산의 최솟값은 1이다.

2에서는 2-1, 2/2만 가능하다 2/3은 불가능

 

3의 연산의 최솟값은 1이다.

3에서는 3-1, 3/3이 가능한데 이 중 최솟값을 골라서 저장하면 되는 것이다. DP[1]<DP[2]이기 때문에 DP[1]을 선택하고

DP[1]+1값을 저장한다.

DP[3]=DP[1]+1

 

위 과정을 반복하면 

DP배열은 이런 식으로 저장된다.

 

N에서 1로 만드는 방법은 위 배열을 이용해서 거꾸로 가면 된다.

10에서 보면 DP[10/3]은 불가능 DP[10/2]는 3의 연산 횟수 DP[10-1]은 2의 연산 횟수 결국 가장 작은 DP[9]가 선택된다. 이런 식으로 DP[1]까지 반복하면 된다.

 

 

#include <iostream>

using namespace std;

int DP[1000001];

int main(void)
{
	int N=0;
	
	cin>>N;
	
	for(int i=2; i<=N; i++)
	{
		int max=987654321;
	
		if(DP[i/3]+1<max&&i%3==0)
		{
			max=DP[i/3]+1;
		}
		if(DP[i/2]+1<max&&i%2==0)
		{
			max=DP[i/2]+1;
		}
		if(DP[i-1]+1<max)
		{
			max=DP[i-1]+1;
		}
		DP[i]=max;
	}
	
	for(int i=1; i<=N; i++)
	{
		cout<<DP[i]<<" ";
	}
	
	cout<<endl;
	
	int i=N;
	
	while(true)
	{
		cout<<i<<" ";
		if(i==1)
		{
			break;
		}
		
		int max=987654321;
		int next=0;
		
		if(DP[i/3]<max&&i%3==0)
		{
			max=DP[i/3];
			next=i/3;
		}
		if(DP[i/2]<max&&i%2==0)
		{
			max=DP[i/2];
			next=i/2;
		}
		if(DP[i-1]<max)
		{
			max=DP[i-1];
			next=i-1;
		}
		
		i=next;
		
	}
	
	return 0;
}