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

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

문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

아이디어 스케치

• 동적계획법을 이용하면 되는 문제이다.
• Bottom-UP 방식으로 2부터 시작해서 N까지 걸리는 최소 횟수를 저장해가면서 풀면 된다.
  
  
  
  

코드 분할 설명

	int N;
	int* dp;	// 동적계획법 알고리즘에 사용할 테이블

	scanf("%d", &N);
	dp = (int*)calloc(N+1, sizeof(int));	// N+1의 인덱스를 갖는 배열 동적할당

• N을 입력 받은 후 N+1개의 인덱스를 갖는 배열을 동적할당 받는다.
• 이때 dp는 동적계획법 알고리즘에서 사용되는 테이블이다.
  
  
  
  

for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + 1;	// 1을 빼는 연산

		if (i % 2 == 0)		// 2로 나누어 떨어질 경우
			dp[i] = min(dp[i], dp[i / 2] + 1);	
		if (i % 3 == 0)		// 3으로 나누어 떨어질 경우
			dp[i] = min(dp[i], dp[i / 3] + 1);
	}

• i = 2부터 시작하는 이유는 i = 1 인 경우에는 연산을 수행하지 않아도 되기 때문이다.
• 1을 빼는 연산은 기존 i에서 -1이 된 값인 i-1까지의 수행된 연산 횟수에 +1을 더해준다. +1을 하는 이유는 -1하는 연산을 한번 수행했기 때문이다.
• 2로 나누어 떨어질 경우에는 현재의 dp[i] 값에 dp[i]까지의 연산 횟수와 2로 나누는 연산을 수행했을 때의 연산 횟수 중 더 작은 값을 저장한다.
• 3으로 나누어 떨어질 경우에는 현재의 dp[i] 값에 dp[i]까지의 연산 횟수와 3으로 나누는 연산을 수행했을 때의 연산 횟수 중 더 작은 값을 저장한다.
  
  
  
  

전체 코드

#include <stdio.h>
#include <stdlib.h>

#define min(a,b) a < b ? a : b

int main()
{
	int N;
	int* dp;	// 동적계획법 알고리즘에 사용할 테이블

	scanf("%d", &N);
	dp = (int*)calloc(N+1, sizeof(int));	// N+1의 인덱스를 갖는 배열 동적할당

	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + 1;	// 1을 빼는 연산

		if (i % 2 == 0)		// 2로 나누어 떨어질 경우
			dp[i] = min(dp[i], dp[i / 2] + 1);	
		if (i % 3 == 0)		// 3으로 나누어 떨어질 경우
			dp[i] = min(dp[i], dp[i / 3] + 1);
	}

	printf("%d", dp[N]);	// 결과 출력

	free(dp);		// 메모리 반환

	return 0;
}

제출 결과