[Java] 백준 #1463 1로 만들기

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

1463번: 1로 만들기

정수 X에 사용할 수 있는 연산 세 가지를 적절히 사용해서 정수 N을 1로 만든다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

연산 사용 횟수의 최솟값 구하기

💡 알고리즘

다이나믹 프로그래밍

💡 접근

RGB거리처럼 모든 케이스의 계산횟수가 동일한 문제가 아니므로, 배열만으로는 해결하기 어려울 것 같다.

→ 재귀함수를 작성하고, 전역변수를 통해 최솟값을 관리하자.

💡 코드

package DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1463 {

    // 재귀함수 <-> 전역변수로 리턴값 관리
    static int res = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        recur(N, 0);
        System.out.println(res);
    }

    static void recur(int num, int cnt){
        // else if문을 쓰면 안됨 !!!!
        if (num == 1){
            res = Math.min(res, cnt);
        }
        if(cnt >= res){
            return;
        }
        if(num % 3 == 0){
            recur(num / 3, cnt + 1);
        }
        if(num % 2 == 0){
            recur(num / 2, cnt + 1);
        }
        recur(num - 1, cnt + 1);
    }
}

💡 정리

• 재귀함수 작성 + 전역변수 관리
• 가능한 모든 경우에 대하여 함수를 호출해야 하므로, else if문을 사용하면 안된다⭐