백준 1463
아무리해도 어떤 식으로 풀어야 할 지 모르겠다가,
(dp 기초문제라는데ㅠㅜㅠㅜㅠㅜㅠㅜ)
일단 모든 경우를 다 따져보는 코드를 먼저 작성해보라는 것과, 상태를 정한 다음 풀이하라는 걸 보고 다음식으로 짜보았다.
>>어떻게 풀지 참고한 블로그
https://zzonglove.tistory.com/13
동적계획법 (Dynamic Programming) 는 어떻게 풀까?
이 포스팅은 Nitish Kumar 의 기사를 참고하여 만들었습니다. [출처] 동적계획법 (Dynamic Programming), DP 는 다항(Polynomial)한 시간안에 특정 문제를 풀기위한 기술입니다. DP 를 이용한 솔루션은 지수형태
zzonglove.tistory.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baekjoon_1463 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int result = make_one(num);
System.out.println(result);
}
static int make_one(int num) {
if(num == 1) {
return 0;
}else {
if( num%2 != 0 && num%3 != 0 ) { //2의 배수도 3의 배수도 아닐때
return make_one(num-1) + 1;
}else if( num%2 == 0 && num%3 != 0 ) { //2의 배수이기만 할 때
int a = make_one(num/2) + 1;
int b = make_one(num-1) + 1;
return Math.min(a, b);
}else if( num%2 != 0 && num%3 == 0 ) { //3의 배수이기만 할 때
int a = make_one(num/3) + 1;
int b = make_one(num-1) + 1;
return Math.min(a, b);
}else { //2와 3의 배수일 때
int a = make_one(num/3) + 1;
int b = make_one(num/2) + 1;
int c = make_one(num-1) + 1;
return Math.min(a, Math.min(b, c));
}
}
}
}....모르는대로 일단 짜보았다. 이클립스에서는 되는데 백준 사이트에서는 시간초과가 나는 코드.
state(n)을 n에서 1이 될 때 걸리는 최소 단계수 로 정의하고 식을 썼다. 모르니까 1부터 전부.
그렇게 했을 때 state(n)이란,
state(n-1) + 1
(n이 3인 경우엔) state(n/3) + 1
(n이 2인 경우엔) state(n/2) + 1
이렇게의 값을 비교해서 최소값을 의미했다.
그런데 생각해보니 저 if-else 문을 간단하게 바꿀 수 있을 것 같다.
길이가 3인 배열을 만들어서 초기값을 state(n-1) + 1로 하고,
3의 배수일 때는 배열 중 하나 값을 state(n/3) + 1,
2의 배수일 때는 배열 중 하나 값을 state(n/2) + 1로 하게 되면
배수 여부와 관계없이 배열에 있는 값들을 비교하면 끝나니까.
다음은 그렇게 고친 코드.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baekjoon_1463 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int result = make_one(num);
System.out.println(result);
}
static int make_one(int num) {
if(num == 1) {
return 0;
}else {
int before = make_one(num-1) + 1;
int[] numArrary = {before, before, before};
if(num%3 == 0) {
numArrary[0] = make_one(num/3) + 1;
}
if(num%2 == 0) {
numArrary[1] = make_one(num/2) + 1;
}
return Math.min(numArrary[0], Math.min(numArrary[1], numArrary[2]));
}
}
}와! 코드 길이는 줄었다!
그리고 메모리 초과가 되었다!
....역시 반복마다 배열을 정의하기 때문이지 않을까, 해서 배열을 빼기로 했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baekjoon_1463 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int result = make_one(num);
System.out.println(result);
}
static int make_one(int num) {
if(num == 1) {
return 0;
}else {
int result = make_one(num-1) + 1;
if(num%3 == 0) {
result = Math.min(result, make_one(num/3) + 1);
}
if(num%2 == 0) {
result = Math.min(result, make_one(num/2) + 1);
}
return result;
}
}
}그리고 다시 시간초과가 되었다!
저 make_one을 더 줄이는 방법은 모르겠어서 여기서 다음 단계로 가기로 했다.
memoization이나 tabulation을 추가하라고 하는데.
Memoization : top-down 접근 방식. cache에 값을 기록.
tabulation : bottom-top 접근 방식. 리스트에 값을 기록.
위 코드의 경우엔 이미 계산한 값을 다른데에서 쓸 경우 또 계산하고 또 계산해서 시간이 오래걸린다고 한다.
이 memoization이랑 tabulation은 그걸 막기 위한 방법.
memoization의 경우 뭔가 값을 계산하면 그걸 배열에 저장해두기만 하면 되는 것 같다. 이 때 값을 계산했다-의 기준은 현재 상태인 num만.
배열 만들어서 초기화 해주고, 이미 계산된 값인지 확인하는 if랑, result는 전부 dp[num]으로 고친 것 이외에는 없다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Baekjoon_1463 {
static int dp[] = new int[1000001];
public static void main(String[] args) throws NumberFormatException, IOException {
Arrays.fill(dp, -1);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int result = make_one(num);
System.out.println(result);
}
static int make_one(int num) {
if(dp[num] != -1) {
return dp[num];
}
if(num == 1) {
return 0;
}else {
dp[num] = make_one(num-1) + 1;
if(num%3 == 0) {
dp[num] = Math.min(dp[num], make_one(num/3) + 1);
}
if(num%2 == 0) {
dp[num] = Math.min(dp[num], make_one(num/2) + 1);
}
return dp[num];
}
}
}하지만 그래도 시간 초과...
여기서
1. 배열을 굳이 num의 최대값으로 줄 필요 없음. num 받아서 거기에 +1만 해주자.
2. dp[1] = 0으로 해두면 make_one 안에서 num==1인 경우 설정할 필요 없다.
거기에 함수 호출의 깊이가 깊어질수록 비효율적이 된다고 한다!
그래서 make_one 호출 전에 for문으로 작은 것부터 make_one 호출하면 더 빨라진다고 함.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Baekjoon_1463 {
static int dp[];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
dp = new int[num+1];
Arrays.fill(dp, -1);
dp[1] = dp[0] = 0;
for(int i = 2; i <= num; i++) {
make_one(i);
}
System.out.println(make_one(num));
}
static int make_one(int num) {
if(dp[num] != -1) {
return dp[num];
}
if(num%3 == 0 && num%2 == 0) {
dp[num] = Math.min(make_one(num-1) + 1, Math.min(make_one(num/3) + 1, make_one(num/2) + 1));
}else if(num%3 == 0) {
dp[num] = Math.min(make_one(num-1) + 1, make_one(num/3) + 1);
}else if(num%2 == 0) {
dp[num] = Math.min(make_one(num-1) + 1, make_one(num/2) + 1);
}else {
dp[num] = make_one(num-1) + 1;
}
return dp[num];
}
}18864kb에 156ms걸림.
하지만 위처럼 for문으로 차근차근 작은 수부터 하게 되주면 memoization을 사용하는 의미가 없다.
memoization은 재귀 함수를 써서 과부하(?)가 일어날 수 있지만 그래도 필요한 값만 계산한다는 장점이 있는데, 위의 코드는 그런 장점을 무시한거니까.
....그런 점에 있어서 위의 코드는 memoization이라기 보다는 tabulation이라고 봐야 맞지 않나 싶다.
재귀를 사용한다고는 하지만 일단 값을 for문을 사용해 채워넣는다는 점에서 재귀될 일이 없을테니까?