[BOJ 1463] 백준 1로 만들기 풀이 - C++ (Dynamic Programming)

사용언어 :  C++

 

 

문제풀이

 * 핵심:dynamic programming이용(https://developing-soosoo.tistory.com/6 dynamic programming 설명은 여기로)

3가지 경우의 수 존재, 3가지 공식을 다 실행해준다 (min을 통해 알아서 최솟값으로 변경해줌)

 

- vector d의 1번째 index값은 0으로 고정 

	vector<int> d(n + 1); //n은 입력값
	d[1] = 0;

 

- for문으로 2부터(1엔 0존재) n이 될 때까지 실행

for (int i = 2; i <= n; i++) {
		//
	}

 

- for문 안에 3가지 경우의 수 작성

//for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + 1; //조건이 없는 -1공식
        if (i % 2==0) //2로 나누어 떨어질 때
			d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3==0) //3으로 나누어 떨어질 때
			d[i] = min(d[i], d[i / 3] + 1);
//	}

전체코드

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
int n;
int main() {
	cin >> n;
	vector<int> d(n + 1);
	d[1] = 0;

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

 

---

총평

처음엔 3가지 경우의 수가 있는데 그 중 어떤 공식을 선택해야 최솟값이 나오나 고민하느라 애썼는데 굳이 그럴 필요 없이 하나하나 다 해보면서 기존의 최솟값(d[index]값)과 비교해 더 작은 값으로 변경해주면 된다는 걸 알고 약간 후련하면서도 허무했다.. ㅎ dynamic programming 관련 문제를 풀어보면서 겉으로 보기엔 각자 다 다른 문제 같았는데 막상 본질은 다 같았다. 신기하면서도 앞으로 내가 숨겨진 본질을 잘 찾을 수 있을지 설렘 반 걱정 반..ㅎㅎ 

---

문제 출처

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

1463번: 1로 만들기