728x90
#include<iostream>
using namespace std;
int dp[1000001];
int min(int a, int b) {
if (a > b) return b; return a;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 3 == 0)
dp[i] = min(dp[i / 3] + 1, dp[i]);
if (i % 2 == 0)
dp[i] = min(dp[i / 2] + 1, dp[i]);
}
cout << dp[n];
}
동적 프로그래밍(DP)이란?
큰 문제를 작은 문제로 분할하여 문제를 푸는 방법.
※ dp[입력] = 연산 사용 횟수
풀이 :
1. 정수 x을 입력받는다.
2. 입력이 1일때는 연산을 사용하지 않아도 되므로 결과 값이 0. 즉, dp[1] = 0;
3. 입력이 2일 때부터 정수 n까지 각각의 연산을 사용하였을 때의 출력 값(=연산 사용 횟수)가 가장 작은 값으로 설정한다.
4. 순차적으로 n까지 계산하게 되고, 결국 마지막엔 n를 입력으로 하였을때의 연산 횟수를 출력한다.
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
백준 1107번 리모컨 <브루트포스> (0) | 2022.07.12 |
---|---|
다익스트라 백준 1238번 파티 (0) | 2022.07.12 |
시뮬레이션 BOJ 3190번 (0) | 2022.07.12 |
[백준/C++] 9012번 괄호 (0) | 2022.07.12 |
[백준/C++] 10989번 수 정렬하기 - 3 (0) | 2022.07.12 |