1로 만들기(1463)

1로 만들기(1463)

import java.io.*;
import java.util.*;

public class Main{
    
  static int[] minCnt = new int[1000001];
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    
    int n = Integer.parseInt(br.readLine());
    
    minCnt[1] = 0;
    
    for(int i = 2; i <= n; i++){
        cal(i);
    }
    
    sb.append(minCnt[n]);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static void cal(int n){
    int tmp1, tmp2;
    
    if(n % 6 == 0){
      tmp1 = 1 + minCnt[n/3];
      tmp2 = 1 + minCnt[n/2];
      
      minCnt[n] = Math.min(tmp1, tmp2);
    }else if(n % 3 == 0){
      tmp1 = 1 + minCnt[n/3];
      tmp2 = 1 + minCnt[n-1];
      
      minCnt[n] = Math.min(tmp1, tmp2);
    } else if(n % 2 == 0){
      tmp1 = 1 + minCnt[n/2];
      tmp2 = 1 + minCnt[n-1];
        
      minCnt[n] = Math.min(tmp1, tmp2);
    } else {
      minCnt[n] = 1 + minCnt[n-1];
    }
  }
}

풀이과정

1. 처음에 경우의 수를 생각할 때, 3으로 나누어질 때랑 -1을 해야할 때는 무조건 하고 2로 나누어질 때는 나누기 또는 -1로 처리하여 결과를 내었다.
2. 그리고 배열을 이용하지 않고 재귀함수를 사용하여 결과값을 찾았다.
3. 첫시도 - 틀렸습니다.
4. 반례를 찾아보다 3으로 나누어질 때도 무조건 3으로 나누는게 빠르지 않을 수 있다고 하였다. 그래서 3으로 나누어 떨어질 때도 분기처리를 시행하였다.
5. 다음 시도 - 시간초과
6. 수들을 적어가며 테스트해봤을 때, 일정 수가 되면 이미 구해진 최소횟수가 있기 때문에 +1만 해도 된다는 것을 알았기에 배열을 이용하여 기록하려고 하였다.
7. 결과 - 틀렸습니다.
8. 3과 2의 최소공배수인 6으로 나누어 떨어질때도 3이냐 2이냐로 결과가 달라질 수 있다고 생각하여 6에서도 분기처리를 시행하였다.

- 성공
- 메모리 : 19660 KB
- 시간 : 156 ms

보안점

1. 내 코드를 보면 6, 3, 2 그리고 나머지 해서 if를 4번 분기하였다.
2. 다른 사람들의 코드를 보니, 어차피 각 항목에는 n-1을 하는 경우가 있었고, 처음 n-1로 값을 도출 한 후 나누기를 했을 경우랑 최소값을 비교하는 식의 코드를 짠 것을 참고하였다.
3. 그리고 굳이 6으로 나눠질 때를 분기처리 하지 않고 최소값을 비교하기 때문에 3과 2로 나누어질 때를 모두 비교하게 하면 자연히 6으로 분기 되었을 때의 로직도 수행하게 되었다.
4. 그리고 나는 일단 배열의 크기를 최대치까지 잡아놨는데, 배열의 크기도 입력받은 n의 크기에 맞춰 생성하는게 더 응답시간과 메모리 측면에서 유리하였다.
5. 모든 걸 수정 후 메모리 18840 KB / 속도 148 ms 가 나왔다.

minCnt[n] = 1 + minCnt[n-1];
        
if(n % 3 == 0) minCnt[n] = Math.min(minCnt[n], minCnt[n/3] + 1);
if(n % 2 ==0 ) minCnt[n] = Math.min(minCnt[n], minCnt[n/2] + 1);