[백준][dp] 1463 1로 만들기 c++ 구현

 

목차

 

 

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

1463번: 1로 만들기

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

다이나믹 프로그래밍의 방법 중 하나인 상향식을 이용해 구현하고자 했다.

다이나믹 프로그래밍의 개념을 모른다면 아래 링크를 참고하면 좋다

https://be-senior-developer.tistory.com/19

[DP] 동적 계획법 알고리즘 c++ 설명

 

 

 

 

문제 풀이 시 주의점

패턴을 찾는 것이 가장 중요한 문제이다 

질문 게시판의 반례를 다 넣어가며 열심히 찾았던 것 같다..

 

 

 

 

문제 풀이

아래 그래프는 1로 만드는 과정을 나타낸 것으로 방법이 여러개인 숫자가 있다.

1										0
2 ->	1									1
3  ->	1									1
4  ->	3  ->	1			4  ->	2  ->	1			2
5  ->	4 ->	2  ->	1							3
6  ->	3  ->	1			6  ->	2  ->	1			2
7  ->	6  ->	3  ->	1		7  ->	6  ->	2  ->	1		3
8  ->	4  ->	2  ->	1		8  ->	4  ->	3  ->	1		3
9  ->	3  ->	1								2
10  ->	9  ->	3  ->	1	10  ->	5  ->	4  ->	2  ->	1		3

 

색칠된 수는 연산의 최솟값이다.

위의 나열해 놓은 수들을 보면 패턴이 있다는 것을 알 수 있다.

 

 

1										0
2 ->	1									1
3  ->	1									1
4  ->	3  ->	1			4  ->	2  ->	1			2
5  ->	4  ->	2  ->	1							3
6  ->	3  ->	1			6  ->	2  ->	1			2
7  ->	6  ->	3  ->	1		7  ->	6  ->	2  ->	1		3
8  ->	4  ->	2  ->	1		8  ->	4  ->	3  ->	1		3
9  ->	3  ->	1								2
10  ->	9  ->	3  ->	1	10  ->	5  ->	4  ->	2  ->	1		3

 

값이 3의 배수일 때를 보자

현재 인덱스를 n이라고 하면 n/3 인덱스 위치의 카운트 +1 값인 것을 볼 수 있다.

 

 

1										0
2 ->	1									1
3  ->	1									1
4->	3  ->	1			4  ->	2  ->	1			2
5  ->	4  ->	2  ->	1							3
6->	3  ->	1			6  ->	2  ->	1			2
7  ->	6  ->	3  ->	1		7  ->	6  ->	2  ->	1		3
8  ->	4  ->	2  ->	1		8  ->	4  ->	3  ->	1		3
9  ->	3  ->	1								2
10->	9  ->	3  ->	1	10  ->	5  ->	4  ->	2  ->	1		3

 

값이 2의 배수일 때를 보자

현재 인덱스를 n이라고 하면 n/2 인덱스 위치의 카운트 +1 값인 것을 볼 수 있다.

 

 

1										0
2 ->	1									1
3  ->	1									1
4  ->	3  ->	1			4  ->	2  ->	1			2
5  ->	4  ->	2  ->	1							3
6  ->	3  ->	1			6  ->	2  ->	1			2
7  ->	6  ->	3  ->	1		7  ->	6  ->	2  ->	1		3
8  ->	4  ->	2  ->	1		8  ->	4  ->	3  ->	1		3
9  ->	3  ->	1								2
10  ->	9  ->	3  ->	1	10  ->	5  ->	4  ->	2  ->	1		3

 

값이 2, 3 의 배수가 아닐 때를 보자

현재 인덱스를 n이라고 하면 n-1 인덱스 위치의 카운트 +1 값인 것을 볼 수 있다.

 

1										0
2 ->	1									1
3  ->	1									1
4  ->	3  ->	1			4  ->	2  ->	1			2
5  ->	4  ->	2  ->	1							3
6  ->	3  ->	1			6  ->	2  ->	1			2
7  ->	6  ->	3  ->	1		7  ->	6  ->	2  ->	1		3
8  ->	4  ->	2  ->	1		8  ->	4  ->	3  ->	1		3
9  ->	3  ->	1								2
10  ->	9  ->	3  ->	1	10  ->	5  ->	4  ->	2  ->	1		3

 

그렇다면 문제인 것이 있다 10일때 최솟값은 4가 아닌 3이라는 것이다.

여기서 2의 배수나 3의배수는 -1을 했을 때가 더 최소의 연산수를

가질 수 있다는 사실을 알 수 있다. 

 

1										0
2 ->	1									1
3  ->	1									1
4  ->	3  ->	1			4  ->	2  ->	1			2
5  ->	4  ->	2  ->	1							3
6  ->	3  ->	1			6  ->	2  ->	1			2
7  ->	6  ->	3  ->	1		7  ->	6  ->	2  ->	1		3
8  ->	4  ->	2  ->	1		8  ->	4  ->	3  ->	1		3
9  ->	3  ->	1								2
10  ->	9  ->	3  ->	1	10  ->	5  ->	4  ->	2  ->	1		3

 

값이 2, 3의 동시 배수일 때를 보자

이때 2, 3 의 배수중 어느 연산을 했을 때 더 최소가 나올지 모르므로

둘 중 계산해서 연산 횟수가 최소가 나오는 값을 선택하면 된다.

1을 뺀 값을 보면 연산 횟수가 오히려 증가하기 때문에 고려에서 제외한다.

 

 

 

 

코드 구현

#include<iostream>
#include<vector>
#include<algorithm>  //min을 쓰기위한 헤더
using namespace std;
vector<int> v(1000000, 0);

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0);
	int n, i;
	cin >> n;
	v[1] = 0;    //1일때 횟수 0따로 추가
	for (i = 2; i <= n; i++) {
		v[i] = v[i - 1] + 1;   //배수가 아닐 때
		if (i % 6 == 0) {    // 2,3 의 배수일 때
			v[i] = min(v[i / 2] + 1, v[i / 3] + 1);
			continue;
		}
		if (i % 2 == 0) {   //2의 배수일 때
			v[i] = min(v[i / 2] + 1, v[i - 1] + 1);

		}
		if (i % 3 == 0) {   //3의 배수일 때
			v[i] = min(v[i / 3] + 1, v[i - 1] + 1);
			
		}

	}

	cout << v[n];
	



}