[Python] 1463 - 1로 만들기

문제

1463번: 1로 만들기

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

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

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

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

입력

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

출력

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

---

풀이

• DP를 이용해 쉽게 풀 수 있는 문제다.

설명

• n부터 거꾸로 내려가며
  • 3으로 나눌때
  • 2로 나눌때
  • 1을 뺄때

  각 경우를 고려해 가장 작은 값을 저장한다.

• 위에서 아래로 차례차례 내려오다보면 O(n)만에 답을 찾을 수 있다.

• 반대로 아래에서 위로 올라오는 것도 가능하다.

답

from sys import stdin, maxsize

input = stdin.readline


def making_1(n):
    DP = [maxsize for _ in range(n)]
    DP.append(0)
    for i in range(n, -1, -1):
        if i*3 <= n: DP[i] = min(DP[i], DP[i*3]+1)
        if i*2 <= n: DP[i] = min(DP[i], DP[i*2]+1)
        if i+1 <= n: DP[i] = min(DP[i], DP[i+1]+1)
    return DP[1]


if __name__ == "__main__":
    N = int(input())
    res = making_1(N)
    print(res)

갑분C++

학부생때 작성한 코드가 있어서 같이 가져왔다.

확실히 C계열이 python에 비해서 성능이 좋은듯하다.

코드길이나 전반적인 로직이 아예 같은데 (방향만 반대) 성능차이가 엄청난다.

#include <iostream>
#include <algorithm>
using namespace std; 
#define MAX 9999999

int N; 
int dp[1000001]; 

int solve() {
	dp[1] = 0; 
	dp[2] = 1; 
	

	for (int i = 3; i <= N; i++) {
		int a=MAX, b = MAX, c = MAX;

		if ((i % 2)==0)
			a = dp[i / 2];
		if ((i % 3)==0)
			b = dp[i / 3]; 
		c = dp[i - 1];
		dp[i] = min(min(a, b), c) + 1; 
	}
	return dp[N]; 
}

int main() {
	cin >> N; 
	cout << solve() << endl;
	return 0;
}

Uploaded by Notion2Tistory v1.1.0