[JAVA] BOJ(백준) - 1로 만들기 - 1463

문제 내용

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

1463번: 1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

---

문제 접근 방법

문제를 처음 접근할때 어떻게든 규칙을 찾으려는 시도를 했다. 그리고 알게된건 딱히 규칙적으로 나오는 식은 없으나 DP문제에 알맞게 전에 계산했던 횟수를 불러온다면 쉽게 계산할 수 있는 문제였다.

그리고 문제를 풀기 위해 dp배열의 인덱스를 입력받는 숫자로, 할당되는 값을 최소횟수라고 생각하고 접근했다.

 

간단하게 예를들면

10은 9 , 3 , 1 로 최소횟수가 3번이고

9는 3 , 1 로 최소횟수가 2번 이다.

 

8은 4 , 2 , 1 로 최소횟수가 3번

16은 8 , 4 , 2 , 1 로 최소횟수가 4번 이된다.

 

15는 5 4 2 1 로 최소횟수가 4번

5는 4 2 1 로 최소 횟수가 3번 이다.

이를통해 알 수 있는 사실은 dp[10] = dp[9] + 1   //  dp[16] = dp[8] + 1  //  dp[15] = dp[5] + 1 이다. 즉,

10의 경우 dp[N] = dp[N-1] + 1

15의 경우 dp[N] = dp[N/3] + 1

16의 경우 dp[N] = dp[N/2] + 1

이 된다.

 

위의 경우를 참고하면 나눌수 있을때 무조건 나누는게 최소횟수가 아니라는 것을 알 수 있다.

그렇다면 나눌수없는 경우엔 N-1을 나눌수 있는 경우엔 나누는 경우와 N-1 하는 경우로 비교해서 더 작은 값을 dp배열에 넣어주면된다.

 

그래서 처음엔 아래처럼 경우를 나눠서 작성했으나 틀렸다고 한다..

if(N%3 == 0) {
	dp[N] = Math.min(findCount(N/3), findCount(N-1))+1;
}else if(N%2 == 0) {
	dp[N] = Math.min(findCount(N/2), findCount(N-1))+1;
}else {
	dp[N] = findCount(N-1)+1;
}

 

그리고 다른 분의 블로그를 참고해보니 2와3으로 둘다 나눌수 있는 6일때의 경우도 고려해야한다고 한다.

마지막으로 위의 조건을 추가해주면 답이 나오게된다.

참고한 블로그( 이분 진짜 너무 잘하는 듯.. )

https://st-lab.tistory.com/133

 

풀이를 보자.

 

---

풀이

package org.boj.dynamic.programming;

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

public class BOJ_1463_1 {
	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		dp = new int[N+1];
		
		for(int i=0; i<=N; i++) {
			dp[i]=-1;
		}
		dp[0]=0;
		dp[1]=0;
		System.out.println(findCount(N));
	}
	
	public static int findCount(int N) {
		if(dp[N]!=-1) {
			return dp[N];
		}
		
		if(N%6 == 0) {//6으로 나눠질땐 2,3으로 나눌때와 -1했을때 비교
			dp[N] = Math.min(findCount(N/2), Math.min(findCount(N/3), findCount(N-1)))+1;
		}else if(N%3 == 0) {
			dp[N] = Math.min(findCount(N/3), findCount(N-1))+1;
		}else if(N%2 == 0) {
			dp[N] = Math.min(findCount(N/2), findCount(N-1))+1;
		}else {
			dp[N] = findCount(N-1)+1;
		}
		
		return dp[N];
	}
}

 

---

마치며

위에는 재귀방식으로 풀었으나 풀이에 쓴 식을 이용하면 for문(ButtomUp)으로 풀 수 있다.

그리고 또다른 블로그를 보면 더간단해 보이는 식으로 풀었고 좋은 풀이법이라 생각들지만 개인적으로 위의 방식이 좀더 알기 쉽다고 생각이든다.