백준 1463번 1로 만들기

- 문제 설명

 

정수 X 에 사용할 수 있는 연산은 3가지 이며, 정수 N 이 주어졌을 때 연산을 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 구하여라

 

연산

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

2. X 가 2 로 나누어 떨어지면, 2 로 나눈다.

3. 1 을 뺀다.

 

 

- 입력

 

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

 

 

- 출력

 

연산을 하는 횟수의 최솟값 출력

 

 

* 문제 풀이의 핵심

 

동적 계획법을 사용해서 어떻게 큰 문제를 작은 문제로 나누어서 해결 할 것인지, 점화식은 어떻게 세울 것인지를 할 수 있어야 풀 수 있는 문제입니다.

 

 

1. 동적 계획법

 

동적 계획법 문제를 풀기 전에 확인해야할 사항 2가지가 있습니다.

 

1) 부분 문제가 겹치는가?

 

2) 작은 문제의 정답이 항상 같은가?

 

위의 2가지 조건을 만족하면 동적 계획법을 사용해서 해결할 수 있는 문제이며, 구현 방법은 Top-Down (재귀), Bottom-Up (for문) 방법 2가지가 있습니다.

 

- DP 문제 풀이 전략 : 풀어야 할 큰 문제 정의 -> 큰 문제를 작은 문제로 만들기 -> 점화식 세우기 -> 2가지 방법 중 하나를 택하여 구현하기

 

 

2. 알고리즘

 

1) 풀어야 할 큰 문제 정의

 

- 큰 문제 : D[N] = N을 1로 만드는 최소횟수

 

=> N 개의 개수 만큼 값을 저장해야 한다. (1차원 배열)

 

 

2) 큰 문제를 작은 문제로 만들기

 

- 작은 문제

 

(1) N -> N/3 : N -> N/3 으로 바뀌는 횟수는 1, N/3 을 1로 만드는 최소횟수 => D[N/3] + 1

 

(2) N -> N/2 : N -> N/2 으로 바뀌는 횟수는 1, N/2 을 1로 만드는 최소횟수 => D[N/2] + 1

 

(3) N -> N-1 : N -> N-1 으로 바뀌는 횟수는 1, N-1 을 1로 만드는 최소횟수 => D[N-1] + 1

 

 

3) 점화식 세우기

 

- 큰 문제는 작은 문제들로 구성되어 있다.

 

- 점화식 : D[N] = min(D[N/3] + 1, D[N/2] + 1, D[N-1] + 1)

 

 

- 소스코드 (Top-Down)

 

#include<iostream>
#include<cstring>

using namespace std;

int d[1000001];

int top_down(int N) {
	if (N == 1) return 0;
	if (d[N] != -1) return d[N];

	d[N] = top_down(N - 1) + 1;

	if (N % 2 == 0) {
		int temp = top_down(N / 2) + 1;
		if (d[N] > temp) d[N] = temp;
	}

	if (N % 3 == 0) {
		int temp = top_down(N / 3) + 1;
		if (d[N] > temp) d[N] = temp;
	}
	
	return d[N];
}

int main() {
	memset(d, -1, sizeof(d));

	int N;
	cin >> N;

	cout << top_down(N) << endl;
}

 

 

- 소스코드 (Bottom-Up)

 

#include<iostream>
#include<cstring>

using namespace std;

int d[1000001];

int bottom_up(int N) {
	d[1] = 0;

	for (int i = 2; i <= N; i++) {
		d[i] = d[i - 1] + 1;
		
		if (i % 2 == 0) {
			int temp = d[i / 2] + 1;
			if (d[i] > temp) d[i] = temp;
		}

		if (i % 3 == 0) {
			int temp = d[i / 3] + 1;
			if (d[i] > temp) d[i] = temp;
		}
	}

	return d[N];
}

int main() {
	memset(d, -1, sizeof(d));

	int N;
	cin >> N;

	cout << bottom_up(N) << endl;
}

 

 

- 문제링크 : www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

- 제출한 코드

Top-Down

 

Bottom-Up

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요