백준 1463번 1로 만들기 (DP)

백준 1463번 1로 만들기를 풀어보자.

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

1463번: 1로 만들기

 

---

 

<풀이>

전형적인 DP문제이며, 우선 DP문제를 풀기 위해 점화식을 세워보자.

연산을 사용하는 횟수의 최소값을 구해야 하므로 아래와 같이 점화식을 세울 수 있다.

D[N] = N을 1로 만들기 위해 사용한 연산의 최소 횟수

이때 사용할 수 있는 연산은 세가지이다.

만약 N이 3이라면 3으로 나눌 수 있고, 나눗셈 연산을 했으므로 연산횟수 1을 더 해준다

ex) D[3] = D[3/3] + 1 -> D[3] = D[1] + 1 

 

이런식으로 각 연산마다 세울 수 있는 점화식은 아래와 같다.

D[N] = D[N/3] + 1

D[N] = D[N/2] + 1

D[N] = D[N-1] + 1

 

위의 점화식에서 최소 연산 횟수를 구해야 하므로 각 연산마다 값을 비교해서 최소값을 구할 수 있다.

bottom-up 방식으로 for문을 통해 D[1] 부터 D[N]까지 값을 채워나간다.

 

<소스코드>

#include &ltiostream&gt

using namespace std;

int main(void) {
	int n;
	int d[1000001] = { 0, };

	cin >> n;

	d[1] = 0;

	for (int i = 2; i <= n; i++){
		d[i] = d[i - 1] + 1;

		if (i % 2 == 0){
			if (d[i] > d[i / 2] + 1){
				d[i] = d[i / 2] + 1;
			}
		}

		if (i % 3 == 0 && d[i] > d[i / 3] + 1){
			if (d[i] > d[i / 3] + 1){
				d[i] = d[i / 3] + 1;
			}
		}
	}

	cout << d[n] << "\n";
}