백준 1463 1로만들기 c++ // dp 하는 방법

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

1463번: 1로 만들기

1. dp 하는 방법

/*
* DP
* 1. 테이블정의
* 2. 점화식 for문 (초기항은 직접구함)
*/

 

1.1 점화식 구하는방법

구체사례를 일반화 하라.

d[12] = d[4]+1 , d[6]+1 , d[11]+1 중 최소값

d[i] = d[i/3]+1 , d[i/2]+1 , d[i-1]+1 중 최소값

 

2. 최소값 구하는 방법(3개숫자 이상일때)

첫번째 값 대입후

새로운 값이 들어올때마다 min (자기자신, 새로운값) 해주면 된다.

d[i] = d[i - 1] + 1;
if (i % 2 == 0) {
    d[i] = min(d[i], d[i / 2] + 1);
}
if (i % 3 == 0) {
    d[i] = min(d[i], d[i / 3] + 1);
}

 

3. 전체코드

#include <bits/stdc++.h>
using namespace std;

/*
* DP
* 1. 테이블정의
* 2. 점화식 for문
*/

//1. d[i] : i를 1로 만드는데 필요한 연산수
//2. d[12] = d[4]+1 or d[6]+1 or d[11]+1
//d[i]= d[i-1]+1 , d[i/2]+1, d[i/3]+1 중 최소값
int d[1000004];
int n;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	d[1] = 0;
	d[2] = 1;
	d[3] = 1;


	for (int i = 4; i <= n; ++i) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0) {
			d[i] = min(d[i], d[i / 2] + 1);
		}
		if (i % 3 == 0) {
			d[i] = min(d[i], d[i / 3] + 1);
		}
	}


	cout << d[n];
}