본문 바로가기
백준

백준 1463: 1로 만들기(java)

by unhyepnhj 2024. 8. 9.

문제


풀이

 

3개의 경우(3으로 나누어떨어짐, 2로 나누어떨어짐, 둘 다 아님) 중 어떤 경우에 어떤 연산을 고려해야 하는지 결정하는 것이 중요한 문제이다.

 

크게 4가지 케이스로 나눌 수 있다.

  1. 3과 2로 모두 나누어떨어질 때: 3으로 나누기/2로 나누기/1 빼기 中 연산 횟수 적은 것 택 1
  2. 3으로만 나누어떨어질 때: 3으로 나누기/1 빼기 中 연산 횟수 적은 것 택 1
  3. 2로만 나누어떨어질 때: 2로 나누기/1 빼기 中 연산 횟수 적은 것 택 1
  4. 1~3 중 해당사항 없을 때: 1 빼기

예제 2의 경우, N=10일 때 3번 케이스이므로, 2로 나누어 10→5→4 →2 →1로 진행할지(연산 횟수: 4) 1을 빼 10 →9 →3 →1(연산 횟수: 3)로 진행할 지 선택해야 한다.

if(arr[N]==null) {
	if(N%6==0) {
		arr[N]=Math.min(min(N-1), Math.min(min(N/3), min(N/2)))+1;
	}
	else if(N%3==0) {
		arr[N]=Math.min(min(N/3), min(N-1))+1;
	}
	else if(N%2==0) {
		arr[N]=Math.min(min(N/2), min(N-1))+1;
	}
	else {
		arr[N]=min(N-1)+1;
	}
    return arr[N];
}

계산 효율을 위해 동적 계획법(dynamic programming)을 사용하였으며, 메모이제이션(memoization)을 위해 배열 arr은 Integer형 전역 변수로 선언하였다. 이 방법을 이용하면 arr[N]이 이미 정해진 경우 중복 연산을 하지 않으므로 시간을 단축할 수 있다.

비교 연산은 별도로 구현하지 않고 Math.min()을 사용하였다.

 

전체 코드

import java.util.Scanner;

public class Main {
	static Integer[] arr;
    
	public static int min(int N) {
		if(arr[N]==null) {
			if(N%6==0) {
				arr[N]=Math.min(min(N-1), Math.min(min(N/3), min(N/2)))+1;
			}
			else if(N%3==0) {
				arr[N]=Math.min(min(N/3), min(N-1))+1;
			}
			else if(N%2==0) {
				arr[N]=Math.min(min(N/2), min(N-1))+1;
			}
			else {
				arr[N]=min(N-1)+1;
			}
		}
		return arr[N];
	}
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		
		int N=scanner.nextInt();
		
		arr=new Integer[N+1];
		arr[0]=arr[1]=0;
		System.out.println(min(N));
	}
}

입력이 1개라 Scanner를 사용했지만 BufferedReader 사용해도 무방하다.

'백준' 카테고리의 다른 글

백준 14244: 트리 만들기(java)  (0) 2024.08.20
백준 9372: 상근이의 여행(java)  (0) 2024.08.19
백준 1874: 스택 수열(java)  (0) 2024.08.07
백준 5397: 키로거(java)  (0) 2024.08.07
백준 1302: 베스트셀러(java)  (0) 2024.08.07