[Baekjoon/백준] 1463번: 1로 만들기(C/C++)

단계별로 풀어보기 15단계(동적 계획법 1) 8번 문제

https://www.acmicpc.net/step/16

동적 계획법 1 단계

---

백준 1463번: 1로 만들기

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

1463번: 1로 만들기

---

문제 설명

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

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

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

---

입력과 출력

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

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

힌트: 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

---

접근 방법

이번 문제는 정수 N을 입력받아 N을 2나 3으로 나누어 떨어지면 나누고, 혹은 1을 빼면서 최종적으로 N을 1로 만드는데 필요한 연산의 최솟값을 출력하는 문제다. 예제 2번과 힌트를 조합해서 보면 10에서 1을 빼고, 3으로 나누고, 또 3으로 나눠서 3이라는 값이 나오게 된다.

만약 N에 1이 입력되면 연산할 필요없으므로 0이 나온다. 2라면 1을 빼면 되므로 1이 나오고, 3이라면 3으로 나눠서 1이 나온다. 4라면 2로 나누고 또 2로 나누면 되므로 2가 나온다. 5는 1을 빼고 2로 나누고 또 2로 나누면 되므로 3이 나온다. 근데 여기서 5의 경우를 보면 사실상 1을 빼는 것만 추가될 뿐, 4와 완전히 같게 계산된다. 즉, 2나 3으로 나뉘지 않는 것은 이전의 값에 1번의 연산이 추가된다고 보면 될 것이다. 이를 식으로 표현하면 arr[i] = arr[i - 1] + 1 이다. 여기에 추가로 2로 나뉘는 것과 3으로 나뉘는 경우 또한 4와 2의 예시처럼 2로 나누는 경우가 하나 더 추가될 뿐이다. 따라서 2로 나뉘는경우에는 arr[i] = arr[i / 2] + 1, 3으로 나뉘는 경우에는 arr[i] = arr[i / 3] + 1이 된다. 이제 이들을 활용해서 최솟값을 구해 저장하고 출력하면 문제를 해결할 수 있다.

이번 문제에서 배열의 크기가 100만이 넘어 동적 할당을 해주었는데, calloc을 사용했다. calloc은 이전 문제에서 사용한 적 있는 memset()이라는 동적할당 배열을 특정 값으로 초기화해주는 함수와 malloc과 합친 것이다. 사용법은 malloc과 거의 동일하다. 자세한 내용은 이 블로그 글을 참고하는 것이 좋을 것 같다.

---

코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000001

int findMin(int x, int y) {
	return x > y ? y : x;
}

int main(int argc, char *argv[]) {
	int N, *arr;
	scanf("%d", &N);

	arr = (int *)calloc(MAX, sizeof(int));	//malloc과 memset(초기화 함수)를 합친 함수

	for (int i = 2; i <= N; i++) {
		arr[i] = arr[i - 1] + 1;
		if (i % 2 == 0)
			arr[i] = findMin(arr[i], arr[i / 2] + 1);
		if (i % 3 == 0)
			arr[i] = findMin(arr[i], arr[i / 3] + 1);
	}

	printf("%d\n", arr[N]);

	free(arr);
	return 0;
}

---

결과

백준 제출 결과