[백준] 1로 만들기 in Java

📍 문제

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

📍 코드 설명

n % 3 ==  0 이면 n/3 , n% 2 == 0이면 n/2, n-1

3가지 연산을 진행해서 가장 빨리 1에 도달하는 연산횟수를 찾는 문제

 

입력의 크기가 1 ~ 10^6이고 시간 제한 0.15초이므로 모든 경우의 수를 계산하면 시간 초과 

직전의 연산 결과를 기억하고 계산하는 DP 문제로 예상가능

 

재귀문제로 접근

1. 종료 조건 : 현재 탐색 횟수 count 가 현재 탐색최소 탐색 횟수 1보다 클 때 굳이 계산할 필요 X

2. n의 초기 값은 integer max => 가장 먼저 1에 접근한 count를 min으로 저장하기 위해

3.  n이 1에 도달시 min과 비교하여 더 작은 값을 min에 저장

4. n/3 , n/2 , n-1 계산

📍 코드

✔️ 코드

import java.util.*;

public class Main
{
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        toOne(n, 0);
        
        System.out.println(min);
    }
    
    static void toOne(int n, int count){
        //현재 coun 최소값보다 크면 굳이 검사할 필요 X
        if(count > min){
            return;
        }
                
        if(n==1){
            min = Math.min(min, count);
        }
        
        if(n % 3 == 0){
            toOne(n/3, count+1);
        }
        if(n% 2== 0){
            toOne(n/2, count+1);
        }
        toOne(n-1, count+1);
    }
}

 

📍 틀린이유

List 사용하여 시간초과

이런 DP 문제는 재귀나 배열을 사용하자