[백준] 1463번 1로 만들기 (C++, JAVA)

1463번: 1로 만들기

DP로 1부터 N까지 차근차근 연산을 사용하는 횟수의 최솟값을 저장해나가면 된다.

 

1. 2의 배수일 경우 -> 2로 나눈 값의 횟수와 1을 뺀 값의 횟수를 구해 비교 뒤 저장

2. 3의 배수일 경우 -> 3으로 나눈 값의 횟수와 1을 뺀 값의 횟수를 구해 비교 뒤 저장

4. 나머지 경우 -> 1을 뺀 값의 횟수를 저장

       

문제에 나와있는 예제를 표로 표현해보면 이렇게 된다.

 

N	횟수
1	0
2	1 + 최솟값(2/2의 횟수, 2-1의 횟수) = 1
3	1 + 최솟값(3/3의 횟수, 3-1의 횟수) = 1
4	1 + 최솟값(4/2의 횟수, 4-1의 횟수) = 2
5	1 + 5-1의 횟수 = 3
6	1 + 최솟값(6/3의 횟수, 6/2의 횟수, 6-1의 횟수) = 2
7	1 + 7-1의 횟수 = 3
8	1 + 최솟값(8/2의 횟수, 8-1의 횟수) = 3
9	1 + 최솟값(9/3의 횟수, 9-1의 횟수) = 2
10	1 + 최솟값(10/2의 횟수, 10-1의 횟수) = 3

 

이대로 구현해주면 끝

 

< C++ 코드 >

#include <iostream>
#include <algorithm>
using namespace std;
int num[1000002] = { 0 };

int main() {
	int N;
	cin >> N;

	for (int i = 2; i <= N; i++) {
		if (i % 2 == 0 && i % 3 == 0) num[i] = 1 + min(num[i / 3], min(num[i / 2], num[i - 1]));
		else if (i % 2 == 0) num[i] = 1 + min(num[i / 2], num[i - 1]);
		else if (i % 3 == 0) num[i] = 1 + min(num[i / 3], num[i - 1]);
		else num[i] = 1 + num[i - 1];
	}
	
	cout << num[N];

	return 0;
}

 

< JAVA 코드 >

import java.util.Scanner;

public class BOJ_1463_1로만들기 {
	static int X, i, dp[];
	
	static int chk(int x) { return i % x == 0 || i < x ? dp[i / x] : 1000001; }
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		X = sc.nextInt(); dp = new int[X + 3];
		for(i = 2; i <= X; i++) dp[i] = Math.min(dp[i - 1], Math.min(chk(2), chk(3))) + 1;
		System.out.println(dp[X]);
	}
}