[백준] 1463번 1로 만들기

단계별로 풀어보기 동적계획법 1의 8번 문제

1463번: 1로 만들기

2020년 1월 21일에 파이썬으로 풀고

n = int(input())
count = 0
li = [0] * (n + 1)
for i in range(2, n + 1):
    temp = []
    if i % 3 == 0:
        temp.append(li[i // 3] + 1)
    if i % 2 == 0:
        temp.append(li[i // 2] + 1)
    temp.append(li[i - 1] + 1)
    li[i] = min(temp)
print(li[n])

두 달 반 뒤인 2020년 4월 6일에 C++로 다시 풀어보았다.

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


int main() {
	int x;
	cin >> x;
	vector<int> dp(x + 1);
	dp[1] = 0;
	for (int i = 2; i <= x; i++) {
		vector<int> v;
		v.push_back(dp[i - 1]);
		if (i % 2 == 0)
			v.push_back(dp[i / 2]);
		if (i % 3 == 0)
			v.push_back(dp[i / 3]);
		dp[i] = *min_element(v.begin(), v.end()) + 1;
	}
	cout << dp[x];
	return 0;
}

역시 C++이 효율적인거로는 최고인 것 같다. 파이썬의 10분의 1도 안 걸렸다.

 

풀이법을 설명하자면

더 큰 수로 나눌 수록 무조건 좋은 건 아니다. 3으로 나누는게 2로 나누는 것보다 더 많이 줄어들기 때문에, 2로 나누는게 1로 빼는 것보다 더 많이 줄어들기 때문에 큰 수로 나눌수록 좋다고 생각할 수도 있는데 그렇지 않다.

예를 들어 10의 경우 10을 2로 나누면 10 -> 5 -> 4 -> 2 -> 1 이렇게 네 번만에 1이 되지만

10에서 1을 먼저 빼면 10 -> 9 -> 3 -> 1 이렇게 세 번만에 1을 만들 수 있다.

따라서 10 / 2인 5가 1로 빨리 가는지 10 - 1인 9가 1로 빨리 가는지 확인해보고 그것을 선택해야 한다.

즉 그것을 미리 구해놓아야 한다. 따라서 동적계획법을 사용해서 가장 작은 계산부터 해서 그 계산을 이용해서 더 큰 계산을 해나가면 된다. 1에서 i로 가는 데 걸리는 연산의 횟수를 구해서 dp[i]에 저장해놓고 dp[i + 1], dp[i * 2], dp[i * 3]은 dp[i] + 1 이런 식으로 구해나갔다. 출력은 dp[x]를 하면 된다.

코드에서 min_element() 함수의 사용법을 모른다면 아래 링크에 있는 포스팅을 참고하면 된다.

https://breakcoding.tistory.com/299

[C++] 벡터, 배열에서 최댓값, 최솟값 찾기 (min_element, max_element)

 

2021년 1월 6일 추가

또 다시 풀어보았다. 코딩을 오래 쉬다가 풀어서 그런가 방법을 생각하는데 하루종일 걸렸다. 그래도 끝까지 아무것도 안 보고 스스로 풀어냈다.

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

int main() {
	int n;
	cin >> n;
	vector<int> dp(n + 1);
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		vector<int> temp;
		if (i % 3 == 0) {
			temp.push_back(dp[i / 3] + 1);
		}
		if (i % 2 == 0) {
			temp.push_back(dp[i / 2] + 1);
		}
		temp.push_back(dp[i - 1] + 1);
		dp[i] = *min_element(temp.begin(), temp.end());
	}
	cout << dp[n];
	return 0;
}

1부터 거꾸로 올라가는 것이다.