백준 / 다이나믹 프로그래밍 / 1463번 / 1로 만들기 / C++

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

 

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 1;
int arr[N] = {0,};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	for(int i=2; i<=n; i++) {
		arr[i] = arr[i - 1] + 1;
		if(i % 3 == 0) {
			arr[i] = min(arr[i], arr[i / 3] + 1);
		}
		if(i % 2 == 0) {
			arr[i] = min(arr[i], arr[i / 2] + 1);
		}
	}
	
	cout << arr[n] << '\n';
	
	return 0;
}

---

일단 나를 제일 괴롭게했던 것 2가지 부터 말하자면, 저 arr[N]을 main함수에 넣으면 안되고 전역변수로 선언해야한다.

아마 스코프의 범위관련 문제인듯한데... 자세한 사항은 더 찾아봐야겠다.

그리고 for문안의 두번째 if문을 else if로 하면 안된다.

3과 2의 공배수인 6의 배수들은 두 조건문에 모두 접근해서 최솟값을 찾아야 하기 때문이다.

 

먼저 알고리즘을 설명하자면, 0으로 초기화된 배열을 만든다.

배열의 원소들은 그 원소의 인덱스가 1이되려면 문제에서 언급한 3가지 연산을 가지고 몇번의 연산이 필요한지이다.

1은 이미 1이므로 연산이 필요없으므로 0이다. (arr[1] = 0, arr[0]도 0으로 초기화)

2는 2를 나누는 연산 한번이므로 arr[2] = 1이다.

3은 3을 나누는 연산 한번이므로 arr[3] = 1이다.

 

위까지는 쉬운데 이제 여기서 앞의것들을 활용할 수가 있다.

메모이제이션 기법이라고 생각하면 쉽다.

2020.09.13 - [ALGORITHM/CodeUp] - CodeUp / Recursion(재귀) / 1930번 / SuperSum / C++

CodeUp / Recursion(재귀) / 1930번 / SuperSum / C++

메모이제이션 관련 간단 설명과 예시문제는 위 문제가 있다.

 

간단히 설명하면 앞에서 계산한 수를 저장해서 나중에 필요할때 저장된것을 가져다 쓰는것이다.

그러면 위를 활용하여 arr[4]는 어떻게 계산할 수 있을까?

4가 1이되려면 일단 2를 두번나눠야 한다.

그런데 4에서 2를 한번나누면 2인데, 우리는 이미 arr[2]값(2의 연산횟수)을 저장해놓았다.

그러면 우리는 4에서 2까지 가는데 2로 나누는 연산 한번만 하면 되므로 arr[4] = arr[2] + 1로 나타낼 수 있다.

 

5는어떨까?

5는 2로도 3으로도 나누어지지 않는다.

따라서 일단 1을빼고 연산을 시작해야하는데, 1을빼면 4가되고 우리는 4의 연산횟수를 저장해놓았다.

따라서 5는 4보다 1을빼는 연산 한번이 더많은 것이므로 arr[5] = arr[4] + 1이다.

 

마지막으로 6의 케이스까지만 보자.

6은 2와 3의 공배수이다.

따라서 2로 나눌수도있고, 3으로 나눌수도있다.

그래서 우리는 먼저 2로 나눌경우, 먼저 3으로 나눌경우 두가지를 봐야하는데,

2로 나누면 3이된다. arr[3] = 1이므로 1 + 1을 해서 2가된다.

3으로 나누면 2가되고 arr[2] = 1이므로 1 + 1을 해서 2가된다.

6은 똑같은 경우이므로 아무조건이나 먼저 연산해도된다.

 

이렇게 1부터 n까지의 1이되기 위한 연산횟수를 저장해가면서 앞에서 쓰는것이다.

여기서 이제 점화식을 구할 수 있는데,

n이 3으로 나누어 떨어질경우

3을 보면 arr[3] = arr[1] + 1이다.

6을 보면 arr[6] = arr[2] + 1이다.

따라서 arr[n] = arr[n / 3] + 1이라고 볼 수 있다.

 

n이 2로 나누어 떨어질경우

2를 보면 arr[2] = arr[1] + 1이다.

4를 보면 arr[4] = arr[2] + 1이다.

6을 보면 arr[6] = arr[3] + 1이다.

따라서 arr[n] = arr[n / 2] + 1이다.

 

2와 3모두 나누어떨어지지 않을경우

어쩔 수 없이 일단 1을 빼고 생각해야한다.

따라서 arr[n] = arr[n - 1] + 1이다.

 

마지막 예외 케이스로 10인경우가 있는데, 2로 나누어떨어진다고 일단 2로 나누고보면

10 / 2 - 1 - 1 - 1 - 1이 되서 연산횟수가 총 5회이다.

하지만 1을 먼저 빼고 연산을 한다면

(10 - 1) / 3 / 3 으로 총 3회이다.

따라서 우리는 나누어 떨어진다고 해도 1을 먼저빼고 연산하는 것과 비교해서 최솟값을 찾은뒤 그 방법으로 해야한다.