백준 1463번 : 1로 만들기

쉬운 문제인줄 알았으나 꽤나 까다로운 문제였다.

탑다운 방식으로 처음에 접근하였으나 실패하였다.

​

바텀업 방식으로 DP 임을 이용해 점화식을 도출하여 푸는 문제!

하지만 점화식도 잘 이해가 되지 않았다.

​

직접 그림을 그려본다.

​

​

N이 1일 경우

1이 되어있으니까 DP[1] = 0 이다

​

N이 2일 경우

2에서 1을 빼는 방법과 2에서 2를 나누는 방법이 있다. 모두 연산은 1번씩!

2에서 1을 빼는 방법의 연산 횟수를 구하는 점화식은 DP[2] = DP[1]+1,

2에서 2로 나누어 연산 횟수를 구하는 점화식은 DP[2/2]+1이다.

​

해석해보면 2에서 2로 나누었기 때문에 +1이 (연산 횟수) 필요하고 앞서 계산한 DP[1]의 최저 연산 횟수가 필요하다.

두 방법 중 연산 횟수가 더 적은 쪽을 선택해야 하기 때문에 min 함수를 사용한다.

​

N이 3일 경우

3에서 1을 빼기 때문에 연산 횟수 = +1 더하기 2에서 1로 만드는 연산횟수

또는 연산 횟수가 1인 3을 3으로 나누는 방법이 존재한다. DP에는 더 작은 연산 횟수인 1을 입력

​

N이 4일 경우

3에서 1을 만드는 연산 횟수 = +1 더하기 4에서 1을 빼기 때문에 연산 횟수 +1

4에서 2를 나누는 연산 횟수 = +1 더하기 2에서 1을 만드는 최저 연산 횟수

​

그리고 두 연산 중 총합이 더 작은 연산 횟수를 DP에 입력!

​

위 처럼 N이 계속 커질 때마다 각 방법에 대해 총 연산 횟수를 구한 뒤 가장 작은 연산 횟수를 선택한다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

//정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
//
//X가 3으로 나누어 떨어지면, 3으로 나눈다.
//X가 2로 나누어 떨어지면, 2로 나눈다.
//1을 뺀다.
//정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.연산을 사용하는 횟수의 최솟값을 출력하시오.

int N;
int DP[1000001];
int cnt = 0;

int main()
{
	memset(DP, 0, sizeof(int) * 1000001);
	cin >> N;

	DP[1] = 0;

	for (int i = 2; i <= N; i++) {
		DP[i] = DP[i - 1] + 1; //1을 뺴는 경우 
		if (i % 2 == 0) DP[i] = min(DP[i], DP[i / 2] + 1); // 2으로 나누어지는 경우 
		if (i % 3 == 0) DP[i] = min(DP[i], DP[i / 3] + 1); // 3으로 나누어지는 경우  
	}

	cout << DP[N] << endl;;
	return 0;
}