백준 1463_1로 만들기(JAVA)

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

[문제 풀이]

DP를 이용하여 문제를 풀었습니다.

 

이 문제는 숫자가 주어 졌을 때 아래와 같은 세가지 규칙을 이용하여 x가 1로 가는 최소 연산의 횟수가 몇번인지를 찾는 문제입니다.

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

문제를 풀기 위하여 DP를 이용하였습니다. 문제에 사용 된 점화 식은 아래와 같습니다.

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);
}	

문제를 푸는 방법은 1 ~ X까지의 연산 최소 횟수를 메모제이션 해줍니다. 메모제이션 하는 방법은 i 번째 수의 값이 (arr[i/2] + 1, arr[i/3] + 1, arr[i-1] + 1) 세개의 값을 비교하여 가장 작은 값을 기록하는 방법입니다.  메모제이션이 끝나면 배열의 X번째 인덱스의 값을 출력합니다.

 

[코드]

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

class Main{

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int x = Integer.parseInt(st.nextToken());	
		
		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]);
	}
	
}