[C++] 백준 1463번 1로 만들기

 

1) 문제설명

 

백준 Online Judge 1463번 1로 만들기

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

1463번: 1로 만들기

 

2) 해결방법

문제를 이해하기 위해서 2부터 하나씩 생각해보았다.

2 -> 1 (2로 나누어 떨어진다) 횟수 : 1

3 -> 1 (3으로 나누어 떨어진다) 횟수 : 1

4 -> 2 -> 1 (2로 두 번 나누어 떨어진다) 횟수 : 2

5 -> 4 -> 2 -> 1 (1을 빼고 2로 두번 나누어 떨어진다) 횟수 : 3

6 -> 3 -> 1 or 6 -> 2 -> 1 (2로 나누고 3으로 나눈다 or 3으로 나누고 2로 나눈다) 횟수 : 2

 

이와 같이 생각하니 (3으로 나눈 것) vs (2로 나눈 것) vs (1을 뺀 것 중)의 최소 횟수로 dp를 설계하면 된다.

3과 2로 둘 다 나누어질 때 -> (3으로 나눈 것) vs (2로 나눈 것) 중 최소 횟수

2로만 나누어 떨어질 때 -> (2로 나눈 것) vs (1을 뺀 것) 중 최소 횟수

3으로만 나누어 떨어질 때 -> (3으로 나눈 것) vs (1을 뺀 것) 중 최소 횟수

 

 

3) 코드

#include<iostream>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>

using namespace std;

long long d[1000001];
int cnt = 0;

/*
d[]는 실행의 최소를 담는다.
*/
int main() {
	int n;
	cin >> n;
	d[2] = 1; // 2를 입력했을때 실행횟수 1번
	d[3] = 1; // 3을 입력했을때 실행횟수 1번
	d[4] = 2; // 4를 입력했을때 실행횟수 2번
	for (int i = 5; i <= n; i++) { // 설정하지 않은것 부터 시작해서 내가 구한것까지 밑에서 위로
		// 실행횟수를 최솟값을 하나씩 다 구한다. => 최종 n이 될떄 실행횟수를 구한다.
		if (i % 2 == 0 && i % 3 == 0) {// 3과 2로 나누어 떨어질 경우 
			d[i] = min(d[i / 2] + 1, d[i / 3] + 1); // 3으로 나눈것/ 2로 나눈 것중에 최소 실행횟수 + 1
		}
		else if (i % 2 == 0) { // 2로만 나누어 떨어질 경우
			d[i] = min(d[i / 2] + 1, d[i - 1] + 1); // 2로 나눈 것/ 하나 뺀 것중에서 최소 실행횟수 + 1
		}
		else if (i % 3 == 0) {// 3으로만 나누어 떨어질 경우
			d[i] = min(d[i / 3] + 1, d[i - 1] + 1);
		}
		else {
			d[i] = d[i - 1] + 1;
		}
	}
	cout << d[n];
}