[BOJ] 백준 [1463,12852] 1로 만들기 1,2 JAVA

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

문제

 

풀이

만약 구하고 싶은 수를 i 라고 하면 , min( dp[i/2]+1 , dp[i/3]+1 , dp[i-1]+1 ) 이라는 최적해를 구해서 하면된다.

연산 순서에 따라 완전 다른 횟수가 나올 수 있기 때문에 그리디로 접근하면 x

 

import java.util.*;
import java.io.*;
 
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());
        int[] dp = new int[10000001];
        dp[0] = dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+ 1;
            if(i%3 == 0)
                dp[i] = Math.min(dp[i/3] +1,dp[i]);
            if(i%2 == 0)
                dp[i] = Math.min(dp[i/2] +1, dp[i]);
        }
        System.out.println(dp[n]);
    }
}
 
 
 
 
 
 

 

 

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

문제

아까 문제랑 동일하다 , 여기에 계산 과정까지 적어주면 된다.

풀이

dp[] 배열과 똑같은 크기의 arr[] 배열을 하나 더 생성 한 다음 , 조건을 만족할 때 arr[i] = i/3 or i/2 or i-1 같이

연속 인덱싱 시켜주면 끝.

 

import java.util.*;
import java.io.*;
 
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());
        int[] dp = new int[10000001];
        dp[0] = dp[1]=0;
        int[] arr = new int[10000001];
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+ 1;
            arr[i] = i-1;
            if(i%3 == 0) {
                if(dp[i/3]+1 < dp[i]){
                    dp[i] = dp[i/3]+1;
                    arr[i] = i/3;
                }
            }
            if(i%2 == 0) {
                if(dp[i/2]+1 < dp[i]){
                    dp[i] = dp[i/2]+1;
                    arr[i] = i/2;
                }
            }
        }
        System.out.println(dp[n]);
        while(n>0){
            System.out.print(n+" ");
            n = arr[n];
        }
    }
}