[백준 1463번] 자바/1로 만들기

 

문제

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

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

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

입력

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

출력

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

---

첫 번째 코드

처음에는 나눌 수 있는 가장 큰 수로 나눈다면 가장 적은 연산 횟수로 1을 만들 수 있을거라고 생각해 아래와 같이 코드를 적었다. 

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

public class BJ1463 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		
		while(n != 1) {
			if(n % 3 == 0) {
				n /= 3;
			} else if(n % 2 == 0) {
				n /= 2;
			} else {
				n--;
			}
			
			System.out.println("현재 n은 " + n);
			cnt++;
		}

		System.out.println(cnt);
		
	}
}

당연히 오답이었고, 제시된 테스트 케이스 중 입력값 10을 통과하지 못하였는데 내 코드의 경우 아래와 같은 n값의 변화를 보여주었지만 생각을 해보니 10 -> 9 -> 1로 갈 경우 3번의 연산만을 통해 n의 값이 1이 됨을 알 수 있었다.

---

두 번째 코드

지난 수업 때 들었던 동적 계획법을 사용하는 문제일거 같다는 생각이 들어서 찾아보았다. 문제를 작은 단위로 쪼개서 생각하기 위해 아래 피보나치 수열처럼 해당문제를 그려보았다.
(https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming)

위 그림을 바탕으로 코드 다시 짜봤다. 바보같이 종료 조건 안써줘서 스택오버플로우 뜸...

---

세 번째 코드

이번에 작성한 코드는 시간초과가 떠버렸다...

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

public class BJ1463 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		System.out.println(calc(n));
	}
	
	private static int calc (int n) {
//		System.out.println("현재 n값: " + n);
		
		int n1 = Integer.MAX_VALUE;
		int n2 = Integer.MAX_VALUE;
		int n3 = Integer.MAX_VALUE;
		
		// 종료 조건
		if(n == 1) {
			return 0;
		} 
		
		// 순환
		if(n % 3 == 0 ) {
			n1 = calc(n / 3) + 1;
		} 
		if(n % 2 == 0) {
			n2 = calc(n / 2) + 1;
		} 
		n3 = calc(n - 1) + 1;
		
		// 세 값중 가장 작은 값 반환
		return getMin(n1, n2, n3);
	}
	
	private static int getMin (int n1, int n2, int n3) {
		if(n1 < n2 && n1 < n3) {
			return n1;
		} else if(n2 < n1 && n2 < n3) {
			return n2;
		} else {
			return n3;
		}
	}
}

---

네 번째 코드

메모이제이션을 사용해보기로 했다! 이를 위해 배열에 담을지, ArrayList에 담을지 고민되었다. 1000000 공간을 배열로 만들어두면 낭비되거같아서.. 그래서 찾아보니 아래와 같이 작성된 코드를 발견하였다. 나도 해시테이블로 해야지! https://velog.io/@chesthyen/%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

으음 메모이제이션 추가하고 이번에는 그냥 틀려버림...^^ 이번엔 뭐가 문젠지 모르겠다 썸원헲미

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

public class BJ1463 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		System.out.println(calc(n, new Hashtable<Integer, Integer>()));
	}
	
	private static int calc (int n, Hashtable<Integer, Integer> memo) {
//		System.out.println("현재 n값: " + n);
		
		int n1 = Integer.MAX_VALUE;
		int n2 = Integer.MAX_VALUE;
		int n3 = Integer.MAX_VALUE;
		
		// 종료 조건
		if(n == 1) {
			return 0;
		} 
		
		// 순환
		if(memo.get(n) == null) {
			if(n % 3 == 0 ) {
				n1 = calc(n / 3, memo) + 1;
			} 
			if(n % 2 == 0) {
				n2 = calc(n / 2, memo) + 1;
			} 
			n3 = calc(n - 1, memo) + 1;
			
			// 가장 작은 값이 memo에 들어감
			memo.put(n, getMin(n1, n2, n3));
		}
		
		return memo.get(n);
	}
	
	private static int getMin (int n1, int n2, int n3) {
		if(n1 < n2 && n1 < n3) {
			return n1;
		} else if(n2 < n1 && n2 < n3) {
			return n2;
		} else {
			return n3;
		}
	}
}

---

다섯 번째 코드

위 코드가 안되는 테스트 케이스를  찾았다. 100000정도의 큰 값은 프로그램이 멈춰버린다. 왜 잘돌아가다가 큰 수가 들어가면 스택오버플로우가 뜰까... 왜 거기 들어가서 나오질 못하니...

10000쯤되면 사실 계속 1씩 작아지는 연산이 최소연산일리 없다 생각해서 우선 조건 걸어버림. 답은 100000은 통과! 이게 맞는건지는 모르겠지만 ?!

하지만 가장 작은 수를 구하는 getMin 메소드에 음수값이 넘어온건지... 저런값이 출력되어버렸다. 마저 예외처리 해주면 진짜 완성일듯????

아니 이게 맞을리가 없지.... 없지...누가 조건을 저렇게 걸어놔...

---

여섯 번째 코드

이번에는 진짜 알거같다!!! 특정한 연산 횟수를 넘어서면 그냥 return을 해주면 스택오버플로우 발생안할듯!!!

... 사실 모르겠다