[BOJ 1463] 1로 만들기

문제

• BOJ 1463
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

DP유형 중 쉬운 난이도의 문제이다. 숫자가 1보다 큰 경우에 연산을 하는 함수DP()를 호출한다. 숫자가 3또는 2로 나누는 경우, 1로 빼는 경우로 총 3가지의 경우의 수가 있으므로 각각을 만족하는 경우 다음 함수를 호출하기 전 연산횟수 cnt를 1증가해야 한다. 여기서, cnt++인 경우 cnt+=1이 되므로 다른 스코프의 cnt에도 영향을 준다. 따라서 반드시 cnt+1을 하여 인자를 전달해야 한다. 모든 연산 수행 후 num==1이 되는 경우 최종 목표를 달성했으므로 이때의 cnt가 Ans보다 작은 경우 Ans에 넣어주고 연산을 종료하고 다른 경우의 수를 본다. 재귀가 깊어지는것을 막기 위해서 연산 중간에 cnt가 Ans보다 크거나 같아지는 경우에는 더 이상 연산을 진행하지 않도록 가지치기 해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int Answer; //최소값
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		Answer = Integer.MAX_VALUE;
		if(num == 1) Answer = 0;
		else dp(num, 0);
		System.out.println(Answer);
	}
	
	static void dp(int num, int cnt){ //숫자, 연산 횟수
		if(num == 1) { //마지막까지 왔으면
			if(cnt <= Answer) Answer = cnt;
			return;
		}
	
		if(cnt >= Answer) return; //계산중인데 최소값보다 크면 더이상 재귀ㄴㄴ
		if(num % 3 == 0) {
			dp(num/3, cnt+1);
		}
		if(num % 2 == 0) {
			dp(num/2, cnt+1);
		}
		if(num > 1) {
			dp(num-1, cnt+1);
		}
	}
}