[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
Comments