[백준] 1463번. 1로 만들기 (C,C++)

문제 설명

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

1463번: 1로 만들기

정수 N(범위는 1~10^6)을 

1. 3으로 나누어 떨어지면 3으로 나눈다

2. 2로 나누어 떨어지면 2로 나눈다

3. 1을 뺀다

이 세가지 방식을 사용하여 정수를 1로 만들고자 할때

위의 연산을 사용하는 최솟값을 출력하라

 

 

 

해결 방법

DP를 활용하여 풀어보자.

arr[]배열을 만든 후 결과값들을 채워넣을 것이다.

 

ex)

arr[1] = N이 1일때 결과값

...

arr[10] = N이 10일때 결과값. arr의 이전값들을 활용해서 값을 찾을것이다.

 

#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS

int main() 
{
	int N;
	scanf("%d", &N);

	int arr[1000001];

	arr[1] = 0;
	arr[2] = 1;
	arr[3] = 1;


	for (int i = 4; i <= N; i++) 
	{
		arr[i] = arr[i - 1] + 1;

		if (i % 2 == 0) 
		{ if (arr[i] > arr[i / 2] + 1) { arr[i] = arr[i / 2] + 1; } }

		if (i % 3 == 0) 
		{ if (arr[i] > arr[i / 3] + 1) { arr[i] = arr[i / 3] + 1; } }
	
	}

	printf("%d", arr[N]);
}

 

1.

N의 범위는 1~10^6이므로

배열 arr[1000001] 을 준비하자

 

 

2.

arr[1]=0  1은 더이상 계산할 필요가없다

arr[2]=1  2는 2로 나누어지므로 1

arr[3]=1  3은 3으로 나누어지므로 1

 

 

3.

arr[i] = arr[i - 1] + 1;

기본적으로 정수 N은 1을 빼면 N-1이 되므로

N-1이 1이되기 위한 최소값(arr[N-1])   +   1   =   N이 1이 되기 위한 값(arr[N]) 이다.

ex)  4 - 1 = 3  →   (1을 뺀다는 행위는 연산을 한번 한다는 것)  →   arr[4] = arr[3] + 1

 

 

하지만 2로 나누어지거나 3으로 나누어지는 경우가

1을 뺄때보다 더 작은 결과값을 낸다면

1을 빼는 것이 최선의 방법이 아닌것이므로

결과값이 바뀐다.

그 경우를 확인해보자

 

 

if (i % 2 == 0) 
{ if (arr[i] > arr[i / 2] + 1) { arr[i] = arr[i / 2] + 1; } }

N이 2로 나누어진다면

N을 2로 나눈 숫자의 결과값(arr[N/2])에 +1을 하면된다 

ex) 10 / 2 = 5  →   (2로 나눈다는 행위는 연산을 한 번 한 것이므로 1을 더한다)  →   arr[10] = arr[5] + 1

 

 

if (i % 3 == 0) 
{ if (arr[i] > arr[i / 3] + 1) { arr[i] = arr[i / 3] + 1; } }

마찬가지로

N이 3으로 나누어진다면

N을 3으로 나눈 숫자의 결과값(arr[N/3])에 +1을 하면된다.

ex) 9 / 3 = 3  →   (3로 나눈다는 행위는 연산을 한 번 한 것이므로 1을 더한다)  →   arr[9] = arr[3] + 1

 

 

물론 2 혹은 3으로도 나누어지지 않는다면

앞전에 "1을 뺀다" 연산을 한 것이 최솟값이 된다.

 

 

4.

printf("%d", arr[N]);

결과값 출력

 

 

+) C++ 풀이

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

int main() 
{
	int n; cin >> n;

	vector<int> dp(1000001);
	dp[1] = 0; 
	dp[2] = 1; 
	dp[3] = 1;


	for (int i = 4; i <= 1000000; i++)
	{
		int count=0;

		dp[i] = dp[i - 1] + 1;

		if (i % 3 == 0) 
		{ 
			count = 1+dp[i / 3]; 
			if (count < dp[i]){dp[i]=count;}
		}
		if (i % 2 == 0) 
		{ 
			count = 1 + dp[i / 2];
			if (count < dp[i]) { dp[i] = count; }
		}
	}

	cout << dp[n];
	
}