[백준] 1463번 1로 만들기(DP_JAVA)

DP로 풀었다가 다르게 풀었다가,

왔다갔다 하다가

결국 DP로 푼 문제!

 

이것도 조건을 제대로 안읽어서

한번에 맞추지는 못했다.

 

---

문제

 

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

1463번: 1로 만들기

 

 

---

설계

 

알고리즘 설계 [접근 방법] : DP

문제를 처음 봤을 때는 반복문으로 무작정 접근했다.

3으로 나눌 수 있으면 나누고, 2로 나눌 수 있으면 나누고 그 다음에는 1을 빼고 풀었다.

그런데 예시의 10을 보고 아예 접근 방법을 다르게 바꾸었다.

현재 내가 가지고 있는 수에서 나누기 3한 값을 1로 만들기 위해서는 연산을 얼만큼 해야 하는지,

나누기 2한 값을 1로 만들기 위해서, 1을 뺀 값을 1로 만들기 위해서는 연산을 얼만큼 해야하는지를 알아야 그 값에서 1을 더한 값이 정답이 된다.

그러기 위해 1부터 n까지 모든 값의 연산 횟수를 알아야 한다. 그래서 DP로 풀었다.

 

풀이과정

1.

n이 1이면 연산과정이 0이므로 0을 출력하고 return한다. 3이하의 값이라면 연산과정이 1이므로 1을 출력하고 return한다.

 

2.

n+1의 크기만큼 배열을 생성하고, 인덱스 1의 값을 1로 저장한다.

 

3.

인덱스 2부터 n까지 반복문을 돌며, 다음 중 가장 작은 값을 현재 인덱스에 저장한다. 

 - i%3이 0일 때, arr[i/3]+1 값

 - i%2가 0일 때, arr[i/2]+1 값 

 - arr[i-1]+1의 값

 

이 3가지의 경우를 비교해서 가장 작은 값을 저장하고, 반복문이 종료되면 arr[n]값을 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_1463_1로만들기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	
		int n = sc.nextInt();
		if(n==1) {
			System.out.println(0);
			return;
		} else if(n<=3) {
			System.out.println(1);
			return;
		}

		int[] arr = new int[n+1];
		arr[1]=0;
		
		for(int i=2; i<n+1; i++) {
			int tmp = Integer.MAX_VALUE;
			
			//1 : 3으로 나눌 수 있으면 3으로 나눈다.
			if(i%3==0) tmp = Math.min(tmp, arr[i/3]+1); 
				
			
			//2 : 2로 나눌 수 있으면 2로 나눈다.
			if(i%2==0) tmp = Math.min(tmp, arr[i/2]+1); 
			
			//3 : 1을 뺀다.
			tmp = Math.min(tmp, arr[i-1]+1); 
			
			arr[i] = tmp;
		}
		
		//출력
		System.out.println(arr[n]);
	}
}

 

 

(❁´◡`❁)

끝!