[백준] 1463 - 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

• 동적 프로그램이을 통해 주어진 입력을 1로 만드는 연산의 횟수를 최소화 하는 문제
• 점화식을 이해할 수 없어 구글링을 통해 풀었음.
• Top-down 방식과 Bottom-up 방식이 있는데, 먼저 Top-down 으로 해결하였음
• Bottom-up 방식을 통해서 상대적으로 메모리를 아낄 수 있는 것을 보인다. (Bottom-up 구현 필요)

---

• Top-Down

 

#include <iostream>
#include <algorithm>
#include <limits.h>

// debug
#define debug_m 1

// size
#define INPUT_MAX	10000000

// macro
#define MIN(a, b) (a < b ? a : b)

// global
int dp[INPUT_MAX + 1];

// method
#if debug_m
void PrintDPArray(int dp[], int input);
#endif

int main()
{
	// init
	std::ios::sync_with_stdio(false);
	std::fill(dp, dp + (INPUT_MAX + 1), INT_MAX);

	// input
	int input = 0;
	(void)scanf("%d", &input);

	// top-down
	dp[input] = 0;
	for (int i = input; i > 0; i--)
	{

		if (0 == (i % 2))
		{
			dp[i / 2] = MIN(dp[i / 2], dp[i] + 1);
		}
		if (0 == (i % 3))
		{
			dp[i / 3] = MIN(dp[i / 3], dp[i] + 1);
		}
		if (2 <= i)
		{
			dp[i - 1] = MIN(dp[i - 1], dp[i] + 1);
		}

#if debug_m
		PrintDPArray(dp, input);
#endif
	}

	// print
	printf("%d\n", dp[1]);

	return 0;
}

void PrintDPArray(int dp[], int input)
{
	
	for (int i = 0; i <= input; i++)
	{
		if (0 == i)
		{
			printf("%d ", i);
		}
		else
		{
			if(INT_MAX == dp[i])
				printf("INF ");
			else
				printf("%d ", dp[i]);
		}
	}
	printf("\n");
}

• Bottom-up

#include <iostream>
#include <algorithm>
#include <limits.h>

// debug
#define debug_m 0

// size
#define INPUT_MAX	10000000
#define DP_ARR_SIZE	3000000

// macro
#define MIN(a, b) (a < b ? a : b)

// global
int dp[INPUT_MAX + 1];

// method
#if debug_m
void PrintDPArray(int dp[], int input);
#endif

int main()
{
	// init
	std::ios::sync_with_stdio(false);

	// input
	int input = 0;
	(void)scanf("%d", &input);
	std::fill(dp, dp + (input + 1), INT_MAX);

	// bottom-up
	dp[0] = dp[1] = 0;
	for (int i = 1; i <= input; i++)
	{
		if (i * 2 <= input)
		{
			dp[i * 2] = MIN(dp[i * 2], dp[i] + 1);
		}
		if (i * 3 <= input)
		{
			dp[i * 3] = MIN(dp[i * 3], dp[i] + 1);
		}
		if (i + 1 <= input)
		{
			dp[i + 1] = MIN(dp[i + 1], dp[i] + 1);
		}
#if debug_m
		PrintDPArray(dp, input);
#endif
	}

	// print
	printf("%d\n", dp[input]);

	return 0;
}

void PrintDPArray(int dp[], int input)
{

	for (int i = 0; i <= input; i++)
	{
		if (0 == i)
		{
			printf("%d ", i);
		}
		else
		{
			if (INT_MAX == dp[i])
				printf("INF ");
			else
				printf("%d ", dp[i]);
		}
	}
	printf("\n");
}

• Bottom-up 다른 방식 (20.01.26 수정하면서 메모리 사용량을 줄였다 (array -> vector) )

//11004 - K 번째 수 (힙 정렬로 해보기)

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <vector>

// debug
#define debug_m 0

// size
#define INPUT_MAX	10000000

// macro
#define MIN(a, b) (a < b ? a : b)

// global
std::vector<int> dp;

// method
#if debug_m
void PrintDPArray(int dp[], int input);
#endif

int main()
{
	// init
	std::ios::sync_with_stdio(false);

	// input
	int input = 0;
	(void)scanf("%d", &input);
	input %= INPUT_MAX;
	dp.resize(input + 1);
	std::fill(dp.begin(), dp.end(),INT_MAX);

	// bottom-up
	dp[0] = dp[1] = 0;
	for (int i = 1; i <= input; i++)
	{
		if (i * 2 <= input)
		{
			dp[i * 2] = MIN(dp[i * 2], dp[i] + 1);
		}
		if (i * 3 <= input)
		{
			dp[i * 3] = MIN(dp[i * 3], dp[i] + 1);
		}
		if (i + 1 <= input)
		{
			dp[i + 1] = MIN(dp[i + 1], dp[i] + 1);
		}
#if debug_m
		PrintDPArray(dp, input);
#endif
	}

	// print
	printf("%d\n", dp[input]);

	return 0;
}

void PrintDPArray(int dp[], int input)
{

	for (int i = 0; i <= input; i++)
	{
		if (0 == i)
		{
			printf("%d ", i);
		}
		else
		{
			if (INT_MAX == dp[i])
				printf("INF ");
			else
				printf("%d ", dp[i]);
		}
	}
	printf("\n");
}