1로 만들기

1로 만들기

---

◎ Problem Definition

1463번: 1로 만들기

---

◎ Implementation

1. Problem Type 

 - Dynamic Programming(Silver 3)

2. Problem Analysis

3으로 나누기, 2로 나누기, 1 빼기 의 수식을 최소한으로 활용하여 숫자 1로 만들기 

- ​DP를 이용하여 다양한 경우의 수에 대한 최소 연산 횟수를 계산합니다. 

3. Solution_1 (☆python)

▶ 완성 코드 

# backjoon : #1463, MakeNumberOne
# date     : 22th, July. 2022
# writer   : Lemonsoda
# reference: https://www.acmicpc.net/problem/1463

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

N = int(input()) # 1 < N < 10^6
dp = [0] * (N+1)

def findmin(cur, next):
    if dp[next] == 0: 
        cnt = dp[cur] + 1
    else:
        cnt = min(dp[next], dp[cur] + 1)
    return cnt

num = N
while num > 1: 
    if num % 3 == 0:
        dp[num // 3] = findmin(num, num//3) 

    if num % 2 == 0:
        dp[num // 2] = findmin(num, num//2) 

    dp[num -1 ] = findmin(num, num-1) 
    num = num - 1
   
print(dp[1])

▶ 성능 

4. Solution_2 (☆cpp)

▶ 완성 코드

// Reference : https://sparklenow.tistory.com/127, https://kau-algorithm.tistory.com/557

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int>dp;

int main() {
	int n;
	cin >> n;
	dp.assign(n + 1, -1);
	dp[1] = 0;
	for (int x = 2; x <= n; x++) {
		int tmp = dp[x - 1] + 1;
		if (x % 2 == 0)
			tmp = min(tmp, dp[x / 2] + 1);
		if (x % 3 == 0)
			tmp = min(tmp, dp[x / 3] + 1);
		dp[x] = tmp;
	}

	cout << dp[n];
	return 0;
}

▶ 성능

---

◎ Results

- 이 문제는 약 7개월 전에 시도해 본 적이 있는 문제입니다만, 다시 보니 또 새롭습니다. 처음에는 3으로 나누어 떨어지는 연산의 횟수를 최소화하면 쉽게 답을 구할 수 있을 것이라 생각했습니다만, 세 연산의 적용을 검토하는 순서는 모든 가능성을 검토해야 하는 문제였습니다. 과거 코드를 확인해보니 Dynamic Programming으로 접근해서 풀었던 문제였습니다. 다시 DP를 이용하여 접근하여 해결했습니다. C/C++ 버전에서는 vector 구조체를 적용하여 유사한 구조로 풀었습니다.