DP(Dynaminc Programming)-1

백준 1463

문제.

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

1463번: 1로 만들기

---

방법.

점화식을 찾고 그 점화식을 코드에 적용시키면 된다.

내가 접근한 방식은 일단 규칙을 찾을려고 노트에 하나씩 봤다.

i	최소 횟수	식
1	0	arr[1] = 0
2	1	arr[2] = 1
3	1	arr[3] = 1
4	2	arr[4] = 1 + arr[i / 2]
5	3	arr[5] = 1 + arr[i - 1]
6	2	arr[6] = 1 + arr[i / 3] or 1 + arr[i / 2]
7	3	arr[7] = 1 + arr[i - 1]
8	3	arr[8] = 1 + arr[i / 2]
9	2	arr[9] = 1 + arr[i / 3]

이렇게 표를 만들다 보니 식 3개를 얻었다.

 

int DP(int num) {
	arr[1] = 0; 						//초기값
	for (int i = 2; i <= num; i++) {
		arr[i] = arr[i - 1] + 1;						
		if (i % 2 == 0) {								
			arr[i] = min(arr[i], arr[i / 2] + 1);
		}
		if (i % 3 == 0 ) {
			arr[i] = min(arr[i], arr[i / 3] + 1);
		}
	}
	return arr[num];
}

위에서 얻은 식을 활용하여 이렇게 코드를 짰다. 

 

표에서 i가 늘어날 때 i에 -1값만 해주고 i의 횟수값을 얻을 수 있다.

이렇게 얻은 횟수와 2나 3으로 나눈 횟수 중 최소을 찾아서 반환 시켜준다.

---

처음 접근했던 방식.

문제에 나온 조건을 코드로 작성했다.

하지만 예제2번인 10을 넣었을 때 횟수가 4번이 나와서 다시 풀어보았다.

---

문제점.

점화식을 구할 생각을 하지 않았다.

 

따라서 점화식을 구하고 규칙이 보이는 식을 찾아서 풀면 된다.

---

해결코드.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1000001] = {0};
int DP(int num);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int num;
	cin >> num;
	cout << DP(num);
	return 0;
}

int DP(int num) {
	arr[1] = 0;
	for (int i = 2; i <= num; i++) {
		arr[i] = arr[i - 1] + 1;
		if (i % 2 == 0) {
			arr[i] = min(arr[i], arr[i / 2] + 1);
		}
		if (i % 3 == 0 ) {
			arr[i] = min(arr[i], arr[i / 3] + 1);
		}
	}
	return arr[num];
}

min함수를 사용하기 위해 algorithm라이브러리 사용.

---