[BAEKJOON] - 1463번 : 1로 만들기

1463번 문제 링크

처음 풀어보는 실버 단계의 DP 문제였다. DP 관련 문제는 재귀함수로 풀어가야 한다는 방식을 어느정도 알고 있었다면 생각보다 쉬웠을 것 같았던 문제였다.

하지만, 아쉽게도 재귀함수를 어떻게 써야하는가에서 고민하다가 결국엔 구현하지 못하고 60분을 초과하게 되었다.

문제를 읽어보면 연산은 크게 3가지의 경우의 수로 나뉜다.

• 3으로 나뉘는 경우
• 2로 나뉘는 경우
• 1을 빼는 경우

위 3가지 연산만 사용하여 1을 만들 때 최소한의 연산 횟수를 찾아내는 문제였다.

내가 초반에 정해진 규칙이 있는지 여부를 확인하기 위해 1부터 10정도까지의 수를 나열해서 카운팅해보았는데, 이상한 점을 발견했다.

원래 2 또는 3으로 나뉘어 떨어지는 정수의 경우, 먼저 나눠주는 것이 횟수를 최소한으로 줄일 수 있을 줄 알았다.

하지만, 10의 수를 연산할 때에는 -1 값을 먼저 해줘야 최소 횟수가 나온다.

10 -> 9 -> 3 -> 1 (4회)
10 ->5 -> 4 -> 2 -> 1(5회)

따라서, 아래의 경우의 수를 추가해줘야 한다.

• 3 또는 2로 나누는 경우, 1을 뺀뒤의 재귀호출한 횟수와 비교 후 최솟값 찾기

추가로, 2와 3의 공배수인 6의 배수인 경우도 포함해줘야 한다.

• 6으로 나뉘는 경우

총 경우의 수

• 2로 나뉜다
• 3으로 나뉜다
• 1을 뺀다
• 6으로 나뉜다
• 2 또는 3,6으로 나뉘느 경우 1을 먼저 뺐을 때, 횟수가 더 적을 수도 있다.

😀 성공

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    
    static Integer[] dp;
    
    public static void main(String[] args)throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        br.close();
        
        dp = new Integer[N+1];
        dp[0] = dp[1] = 0;
        
        System.out.println(recur(N));
    }
    
    static int recur(int N){
        
        if(Objects.isNull(dp[N])){
            // 6으로 나눠지는 경우
            if(N % 6 == 0){
                dp[N] = Math.min(recur(N-1),Math.min(recur(N/3),recur(N/2)))+1;
            }
            // 3으로만 나눠지는 경우
            else if(N % 3 == 0){
                dp[N] = Math.min(recur(N/3), recur(N-1))+1;
            }
            // 2로만 나눠지는 경우
            else if(N % 2 == 0){
                dp[N] = Math.min(recur(N/2), recur(N-1))+1;
            }
            // 2와 3으로 나뉘지 않는 경우
            else{
                dp[N] = recur(N-1)+1;
            }
        }
        
        return dp[N];
    }
}

하지만, 놀랍게도 이것보다 더 성능이 좋은 로직을 구현한 부분도 있었다.
아래 로직에 대한 설명은 참고 로직을 참고 바란다.

💪 자극 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
		System.out.println(recur(N, 0));
	}
 
	static int recur(int N, int count) {
		// N이 2 미만인 경우 누적된 count값을 반환
		if (N < 2) {
			return count;
		}
		return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
 
	}
}

참고 링크
https://st-lab.tistory.com/133