728x90
문제
https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
문제이해
- 첫째 줄에 N을 입력합니다.
- 연산 횟수의 최솟값을 출력합니다.
이 문제는 다이나믹 프로그래밍을 이용해야 합니다. 배열을 통해 설명해 보겠습니다. dp [i]는 i를 1로 만드는데 걸리는 연산 횟수의 최솟값을 의미합니다.
dp [2]와 dp [3]은 당연히 1입니다.
dp [4]의 경우 dp [2]에 1을 더한 값 또는 dp [3]에 1을 더한 값인 2입니다.
dp [5]는 5 - 1 = 4, 4 - 1 = 3, 3 / 3 = 1 또는 5 - 1 = 4, 4 / 2 = 2, 2 / 2 = 1 이러한 연산 과정을 통해 3이라는 값을 가집니다.
이렇게 dp [i]는 dp [i-1] 또는 가능하다면 dp[i / 2] 또는 dp [i/3]의 값 중 가장 작은 값에 1을 더한 값을 가지게 됩니다.
이를 코드로 표현하면 다음과 같습니다.
문제풀이
#include <iostream>
#include <vector>
#include <cmath>
#define MIN 1000001
using namespace std;
vector<long long> dp(MIN);
void method() {
dp[2] = 1;
dp[3] = 1;
for (int i{ 4 }; i < dp.size(); i++) {
int min{ MIN };
if (i % 3 == 0)
if (dp[i / 3] <= min)
min = dp[i / 3];
if (i % 2 == 0)
if (dp[i / 2] <= min)
min = dp[i / 2];
if (dp[i - 1] <= min)
min = dp[i - 1];
dp[i] = min + 1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
method();
int N;
cin >> N;
cout << dp[N];
}
문제후기
어렵지 않은 문제였습니다.
728x90
'Coding' 카테고리의 다른 글
[C++]백준 1715번: 카드 정렬하기 (0) | 2023.08.08 |
---|---|
[C++]백준 5014번: 스타트링크 (0) | 2023.08.03 |
[C++]백준 11727번: 2xn 타일링 2 (0) | 2023.08.02 |
[C++]백준 11726번: 2xn 타일링 (0) | 2023.08.01 |
[C++]백준 11286번: 절댓값 힙 (0) | 2023.08.01 |