200917 목 [BOJ] 1463

kyuhyun·2020년 9월 17일
0

1일1고리즘

목록 보기
5/20

BOJ 1463

❗ 단순 반복문, 조건문으로는 최소 횟수 를 산출할 수 없음!
❗ 무조건 큰 수로 나눠버리는게 최선이 아님!!!

// 너무 단순하게 생각한 반복문
    int cnt = 0;
    	
    while (N != 1) {
    	if (N%3 == 0) N = N/3;
    	else if (N%2 == 0) N = N/2;
    	else N -= 1;
    	cnt++;
    }

🔑 인덱스가 0부터 입력된 수까지 모든 수를 나타내는 배열을 생성하고, 각각 1이 되는 최소횟수를 값으로 가진다.

💡 Top-Down은 재귀함수

(출처 : https://odysseyj.tistory.com/19)

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

public class Main {
	
	public static int d[];
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	br.close();

    	d = new int[N+1];
    	
    	System.out.println(dp(N));
    }
    
    public static int dp(int N) {
    	if (N == 1)
    		return 0;
    	if (d[N] > 0)
    		return d[N];
    	
    	d[N] = dp(N-1) +1;
    	if(N%3 == 0)
    		d[N] = Math.min(d[N], dp(N/3)+1);
    	if(N%2 == 0)
    		d[N] = Math.min(d[N], dp(N/2)+1);
    	return d[N];
    }
}

💡 Bottom-Up은 반복문을 이용한 방식으로, base case부터 값을 다 찾으면서 원하는 값에 도달하는 것

(출처 : https://odysseyj.tistory.com/19)

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

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	br.close();

    	int dp[] = new int[N+1];
    	dp[0] = 0;
    	dp[1] = 0;
    	
    	for(int i=2;i<=N;i++) {
    		dp[i] = dp[i-1] + 1;
    		if(i%2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
    		if(i%3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
    	}
    	System.out.println(dp[N]);
    }
}

DP를 스스로 풀지 못해 결국 구글링해버렸다..
그래도 어떤 식으로 풀이 코드를 이해하긴 했으니, 조금씩 구글링을 줄여가면서 DP를 풀어보자.
(근데 둘 다 출력시간은 어마어마하네...)


profile
알고리즘은 즐거워

0개의 댓글