[Algorithm] 백준 1463(dp 문제)

Syeon2·2022년 12월 18일
0

Algorithm

목록 보기
19/28
post-thumbnail

📌 문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

  • 거의 반년만에 재귀를 사용한 Dynamic Programming 문제를 접하는 것 같다. 초반에 어떻게 풀지 고민했으나 다행스럽게 어떤 방향성을 가지고 풀어야할 지 떠올라 구현해보았다.
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static int min = Integer.MAX_VALUE;
    
	public static int recur(int num, int count) {
    	if (num == 1 || count >= min) {
        	min = count;
            return count;
        }
        
        if (num % 3 == 0 && num % 2 == 0) {
        	int a = recur(num / 3, count + 1);
            int b = recur(num / 2, count + 1);
            int c = recur(num - 1, count + 1);
            
            return Math.min(a, Math.random(b, c));
        } else if (num % 3 == 0) {
        	int a = recur(num / 3, count + 1);
            int b = recur(num - 1, count + 1);
            
            return Math.min(a, b);
        } else if (num % 2 == 0) {
        	int a = recur(num / 2, count + 1);
            int b = recur(num - 1, count + 1);
            
            return Math.min(a, b);
        } else {
        	return recur(min - 1, count + 1);
        }
    }

	public static void main(String[] args) {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.valueOf(br.readLine());
        
        System.out.println();
    }
}
  • 처음에는 문제를 잘못 이해해서 단순히 주어진 상수에서 조건 1, 2, 3번을 Recursive할 때마다 순차적으로 검사하는 방식이라고 잘못 이해했다.
  • 하지만 문제에서 요하는 것은 3가지의 방법을 조건에 만족하는한 아무때나 적용가능하고 제일 적은 연산을 하는 경우의 연산 수를 구하는 것이었다.

  • 그래서 생각했던 것은 각 조건에서 사용할 수 있는 방법들을 Recursive한 값을 구했다. (a, b, c..) 그리고 최소값을 저장할 수 있는 class static 변수를 만들어서 값을 저장하고 값을 초과하면 어김없이 return을 하는 방법이다. 다행히 테스트 케이스를 통과했지만 생각보다 시간이 걸린 것 같았다.
    내 코드 시간 : 190ms, 제일 빠른 코드 : 120ms

  • 다른 사람의 코드를 참고해보니 매우 간단해보여서 어떻게 구했는지 분석해보았다.

public static int recur(int num, int count) {
	if (num < 2) {
    	return count;
    } else {
    	return Math.min(
    	    recur(num / 2, count + 1 + (num % 2)),
	        recur(num / 3, count + 1 + (num % 3)));
    }
}
  • 처음이 이 코드를 보고 의문이 들었던 부분은 3방법인 num - 1은 언제하지?의 의문이었다. 그리고 recursive하는 count parameter에는 count + 1 + (num % 2)가 들어가 있는데 이게 멀까 싶었다.

  • 몇번 살펴보니 내 코드를 굉장히 잘 압축시킨 풀이법이었다. recur에 들어가는 num / 2, num / 3은 기존의 3가지 방법 중 2가지를 적용하였다. 그리고 count + 1 + (num % 2(3))은 혹여나 나누어떨어지지 않는 수였다면 어차피 -1하고 count도 증가하기 때문에 일일히 -1 recursive를 적용할 필요없이 바로 count를 증가시키는 방법이다. 이러한 방법으로 반복적으로 수행해야할 코드들이 많이 줄어들어 결국 시간도 최소화할 수 있었다.

profile
공부한 것을 기록합니다📝

0개의 댓글