백준 1463 1로 만들기

hyeon·2023년 2월 1일
0

알고리즘 연습

목록 보기
19/23

문제 링크

1463 1로 만들기
실버 3
dp

풀이

일단 무지성 완탐 시도.. 실패->
표를 만들어서 규칙을 찾기 시작-> i2 i3 은 dp[i/2] 와 dp[i/3]와 같다는 것을 발견 -> 나머지는 dp[i-1]와 같다는 것을 발견
=> 실패
dp[i-1]이 dp[i/2] dp[i/3]보다 더 작을 경우가 있었고 공배수일때는 무조건 /3으로 하는게 최솟값에 가까울것같았지만 /2으로 하는게 더 작을 경우가 있었다 (아마 642일때 답 10) 그래서 결국 /2 /3 -1인 경우를 모두 살펴봐야했다.

코드 (java)

더러운 버전


public class 백준1463 {
    public static Scanner scan=new Scanner(System.in);
    public static StringBuilder sb=new StringBuilder();
    public static int min=Integer.MAX_VALUE;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=scan.nextInt();
        sol(n);
    }
    
    public static void sol(int n) {

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

}

더 깔끔한 버전

배열을 max값으로 채우고 i/2 i/3 i-1모두 체크해보기 시간상 큰 차이는 없음

import java.util.Arrays;
import java.util.Scanner;

public class 백준1463 {
    public static Scanner scan=new Scanner(System.in);
    public static StringBuilder sb=new StringBuilder();
    public static int min=Integer.MAX_VALUE;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n=scan.nextInt();
        sol(n);
    }
    
    public static void sol(int n) {

        int []dp=new int [n+4];
        Arrays.fill(dp, Integer.MAX_VALUE-1);
        dp[1]=0;
        dp[2]=1;
        dp[3]=1;
        for(int i=4;i<=n;i++) {
            if(i%3==0)  dp[i]=Math.min(dp[i], dp[i/3]+1);
            if(i%2==0)  dp[i]=Math.min(dp[i], dp[i/2]+1);

            dp[i]=Math.min(dp[i], dp[i-1]+1);
            
        }
        System.out.println(dp[n]);
    }

}
profile
남기고 싶은 개발자입니다 :>

0개의 댓글