[BOJ 1463] 1로 만들기 (java)

문제 링크 https://www.acmicpc.net/problem/1463

1) Top-down 풀이

package basics_400;

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

//Top-down 
//재귀 -> 큰 문제를 작은단계로 쪼개고, 작은 문제를 합치며 정답을 구하는 방식 
public class BOJ1463 {
	//계산된 값을 메모하는 배열 
	static int[] memo;
	static int temp = 0;

	//DP - 단계를 한번 수행하는 1과 나머지를 생각하면 편하다.
	//n -> 1 로 만드는 함수 
	static int makeOne(int n) {
		// n이 1이라면 1을 만드는 방법이 0개
		if (n == 1)
			return 0;
		
		// 이미 계산이 되어있다면 계산된 값을 돌려줌 
		if (memo[n] > 0)
			return memo[n];

		//연산을 통해 횟수 구하는 과정 
		// 3. 1을 빼는 연산
		memo[n] = 1 + makeOne(n - 1);

		// 2. 2를 나누는 연산
		if (n % 2 == 0) {
			temp = 1 + makeOne(n / 2);
			//1을 빼서 구했던 값과 2를 나누는 연산으로 구한 값을 비교 
			//더 작은 최소 값으로 갱신 
			if (memo[n] > temp)
				memo[n] = temp;
			
			//1. 3을 나누는연산 
		}if(n % 3 == 0) {
			temp = 1+ makeOne(n / 3);
			//1을 빼서 구했던 값과 3을 나누는 연산으로 구한 값을 비교 
			//더 작은 최소 값으로 갱신 
			if(memo[n]>temp)
				memo[n] = temp;
		}

		//저장된 최소값을 리턴 
		return memo[n];

	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		memo = new int[n+1];
		System.out.println(makeOne(n));
	}

}

2) Bottom-up 풀이

package basics_400;

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

//Bottom-up
//반복문 -> 작은 문제를 모아서 큰 문제를 해결 
public class BOJ1463_2 {
	static int[] memo;

	static int makeOne(int n) {
		
		//1일때는 0가지기 때문에 0을 미리 넣어줌 
		memo[1] = 0;
		
		//1일때는 이미 값을 넣었으니 2부터 n까지 반
		for(int i=2;i<=n;i++) {
			// 3. 1을 빼는 연산 먼저 수행해서 메모 
			
			memo[i] = 1+memo[i-1];
			
			// 2. 2를 나누는 연산 , 1을 뺀 결과 값과 비교해서 더 작으면 갱
			if(i%2==0&& memo[i] > 1+memo[i/2]) {
				memo[i] = memo[i/2]+1;
				
			// 3. 3을 나누는 연산 , 1을 뺀 결과 값과 비교해서 더 작으면 갱
			}if(i%3==0 && memo[i] > 1+memo[i/3]) {
				memo[i] = memo[i/3]+1;
			}
		}
		//저장된 최소값 리턴 
		return memo[n];

	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		memo = new int[n+1];

		System.out.println(makeOne(n));
	}

}

---

n을 하나 입력 받을 때 BufferedReader 의 read() 의 반환형이 int 라서 숫자하나 받아오는건줄 알고 썼다.

하지만 출력 결과가 갑자기 커졌는데 그 이유는 int형 숫자를 읽어오는 것이 아닌, txt형식으로 저장된 ASCII 형식의 문자값을 읽어오는 것이라고 한다..

그래서 br.read를 사용하려면 br.read() -48; br.readLine(); 을 쓰거나 Integer.parseInt(br.readLine()); 을 써야한다고 함

평소에 쓰던 뒤에거 쓰자 ㅎ

---

참고 : https://www.acmicpc.net/board/view/9744