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인 경우를 모두 살펴봐야했다.
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]);
}
}