[백준] 1로 만들기 in Java

📍 문제

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

 

정수 N이 주어졌을 때 

1. 3으로 나누거나

2. 2로 나누거나

3. 1로 빼서

가장 적게 연산을 하여 1로 만드는 횟수를 구하는 문제이다.

 

bfs로 /3 /2 -1해서 가장 빨리 1에 도착하는 방법으로도 풀 수 있을 것 같다.

하지만 좀만 고민해본다면 dp로 풀 수 있고 dp가 시간 복잡도 깡패이므로 dp로 풀겠다.

📍 코드 설명

n=1일 때 : 0이다

n=2일 때 : 2/2를 하면 1이므로 1이다

n=3일 때 : 3/3을 하면 1이므로 1이다

n=4일 떄 : 4/2 = 2, 2/2 = 1이므로 2이다

n=5일 때 : 5-1 = 4, 4/2 = 2, 2/2=1 이므로 3이다

n=6일 떄 : 6/3 = 2, 2/2 = 1이므로 2이다.

n=7일 때 : 7-1 = 6, 6/3 = 2, 2/2 = 1이므로 3이다

.

.

.

이렇게 계산을 하다보면 과거에 계산한 방법을 그대로 사용하는 것을 볼 수 있다.

그렇다면 배열 arr에 n이 1이 되기 위해 최소 몇 번 연산했는지 저장해놓는다면 dp로 답을 구할 수 있다.

📍 코드

✔️ 코드

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int x = Integer.parseInt(br.readLine());
		
		int[] arr = new int[x+1];
		arr[1] = 0;
		for(int i = 2; i <= x; i++) {
			arr[i] = arr[i-1] + 1;
			if(i % 2 == 0) {
				arr[i] = Math.min(arr[i], arr[i/2] + 1);
			}
			if(i % 3 == 0) {
				arr[i] = Math.min(arr[i], arr[i/3] + 1);
			} 
		}
		
		System.out.println(arr[x]);
	}
}

 

이 때, i-1은 모든 값이 수행할 수 있으므로 전부 계산하고

만약 /2, /3이 가능하다면 그 전의 값들이 최소연산인 경우에만 arr[i]에 넣기 위해 Math.min으로 비교하여 연산을 수행한다.

 

📍 틀린이유

DP인 것 같은데 정확히 DP 점화식을 구현하는 게 가장 어려운 것 같다

 

📍 기억할 것

항상 헷갈릴 때는 1부터 최대 10까지는 천천히 손으로 구해본다.

그렇다면 규칙과 점화식이 보일 때가 많다.