[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 1로 만들기 (1463)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 1로 만들기 (1463)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 1로 만들기 (1463) 

 

---

 

[문과 코린이의 IT 기록장] C++ 알고리즘 - 동적 계획법(Dynamic Programming)

1463번: 1로 만들기

[ 문제 ]

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

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

[ 입력 ]

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

[ 출력 ]

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

---

- 문제의 목표를 반영, 점화식 : DP[a] = b

a를 1로 만드는데 취해야 하는 최소연산개수는 b번이다.

 

- N부터 1까지 감소하는 방식으로 생각하지 말고, 1부터 N까지 증가하는 방식이라고 생각해보자

N/3 -> N x 3 연산이 수행되어야 할 것 N/2 -> N x 2 연산이 수행되어야 할 것 N-1 -> N + 1 연산이 수행되어야 할것

DP[1] = 0

DP[2] = 1 (최소값)

: 1+1 (1번의 연산) = DP[1] +1

: 1x2 (1번의 연산) = DP[1] x 1

DP[3] = 1 (최소값)

: 1+1+1 (2번의 연산) = DP[2] + 1

: 1x2+1 (2번의 연산) = D[2] + 1

: 1x3 (1번의 연산) = DP[3/3 = 1] x 3

DP[4] = 2 (최소값)

: 1+1+1+1 = DP[3]+1

: 1x2+1+1 = DP[3] +1

: 1x3+1 = DP[3]+1

: (1+1)x2 = DP[4/2 = 2]+1

: (1x2)x(1x2) = DP[4/2 = 2] x DP[4/2/ = 2]

.

.

.

DP[N] = min(DP[N-1]+1, DP[N/2]+1, DP[N/3]+1)

 

 

---

[ 코드 ]

1) Top-down 방식

#include <iostream>
using namespace std;

int memo[1000001];
int Func(int n) {
	if (n == 1) // 1을 만드는 것이므로, 연산횟수 0
	{
		return 0;
	}
	if (memo[n]>0) // 이미 호출되었었던 값이면, 그대로 반환
	{
		return memo[n];
	}
	
	// Func를 타고 계속 올라가서, memo[1]부터 하나씩 return하며 memo[n]까지 값을 할당하는 과정이라고 생각
	memo[n] = Func(n - 1) + 1; // 이는 -1을 했을 때의 연산 개수
	// -1는 n!=1이면 모두 실행할 수 있음 
	// +1은 이번에 memo[n]을 만들기 위해 수행되는 연산 개수 추가
    // 즉 +1은 최소 연산횟수가 1개 증가한다는 의미

	// 만약 n의 값이 2로 나눠질 때 연산해보기
	if (n%2 == 0)
	{
		int temp = Func(n / 2) + 1; // 2로 나눠졌을 때의 연산 개수 (+1은 최소 연산개수가 1개 증가한다는 의미)
		if (memo[n] > temp) // 최소값을 구하기 위해 비교하는 과정 (기존의 memo[n]값과 비교 가능)
		{
			memo[n] = temp;
		}
	}

	// 만약 n의 값이 3으로 나눠질 때 연산해보기
	if (n%3 == 0)
	{
		int temp = Func(n / 3) + 1; // 3로 나눠졌을 때의 연산 개수
		if (memo[n] > temp) // 최소값을 구하기 위해 비교하는 과정
		{
			memo[n] = temp;
		}
	}

	return memo[n];
	// memo[1]부터 memo[n]까지 각각의 재귀함수, 함수에서 return 해주는 역할

}

int main() {
	int N; // 정수 N
	cin >> N;

	cout<< Func(N);
	return 0;
}

2) Bottom-up방식

#include<iostream>
using namespace std;

int dp[1000001];
int func(int n) {
	if (n == 1) // 1을 만드는 것이므로, 연산횟수는 0이라고 말할 수 있음/
	{
		return 0;
	}

	for (int i = 2; i <= n; i++) // memo[2]부터 memo[n]까지 하나씩 구해가면서 최소연산횟수 구함
	{
		dp[i] = dp[i - 1] + 1; // 하나 작은 값보다 +1 (가장 기본)
		if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) // dp[i/2]+1은 2로 나누었을 때의 연산횟수
		{
			dp[i] = dp[i / 2] + 1;
		}
		if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) // dp[i/3]+1은 3로 나누었을 때의 연산횟수
		{
			dp[i] = dp[i / 3] + 1;
		}
	}
	return dp[n];
}


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

	cout << func(N);
	return 0;
}

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)