C++ / 1463 / 1로 만들기 ( 다이나믹 프로그래밍 )

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

문제 요약

정수 x가 있을 때 사욯 할 수 있는 연산은 다음과 같이 세 가지가 있습니다.

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

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

3. 1을 뺀다.

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

문제 풀이

1. n을 입력받고 벡터를 n+1 크기로 정의 합니다.2. 벡터의 1번 인덱스를 0으로 초기화 합니다. ( 1이 1로 되는데 필요한 연산의 횟수는 0회 )3. 반복문으로 최소 횟수를 구합니다.4. 2부터 연산을 시작하는데 v[ i - 1 ] +  1; 로 연산을 하는 이유는 i-1 == 1 입니다. 1은 0회를 가지고 있습니다. 거기다가 2가 1이 되는데 필요했던 횟수 1을 더해서 2는 1회를 갖게됩니다.5. 위에서 구한 횟수를 2로 나누어질 경우 v[ i /  2 ] + 1; 과 비교해서 작은 값을 v[ i ]에 넣게 됩니다. v[ i /  2 ] + 1; 이것도 똑같이 i / 2인 숫자의 횟수에다가 나누기 2를 한 횟수 ( + 1 )을 해주는 겁니다.6. 3으로 나누어 떨어지는 경우에도 i / 3을 한 숫자에 나누기 3을 했던 횟수 ( + 1 )를 해줘서 기존의 값과 더 작은 값을 저장합니다.7. 이렇게 하면 n일 경우까지 1이 되는 최솟값이 쌓이게 됩니다.8. v[n]  을 출력합니다.

주의할 점

이 문제는 다이나믹 프로그래밍 알고리즘 중 bottom-up 방식을 사용해 풀 수 있습니다.다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 문제라고 할 수 있습니다.그 중에 bottom-up 방식은 가장 작은 문제들로 부터 답을 구하며 전체 문제의 답을 찾는 방식입니다.재귀 호출을 사용하지 않기 때문에 시간 복잡도를 줄일 수 있습니다.

코드

#include<iostream>
#include<vector>

using namespace std;

int n;
vector<int> v;
int main()
{
cin >> n;
v.resize(n + 1);
v[1] = 0;
for (int i = 2; i <= n; i++)
{
// 1을 뺐을 때
v[i] = v[i - 1] + 1;
// 2로 나누어 졌을때
if (i % 2 == 0) v[i] = min(v[i], v[i / 2] + 1);
// 3으로 나누어 졌을때
if (i % 3 == 0)v[i] = min(v[i], v[i / 3] + 1);
}
cout << v[n];
return 0;
}

반응형

예제 1

2

결과 1

예제 2

10

결과 2