[알고리즘] 백준 알고리즘 1463

 

사용언어: JAVA

 

 

문제해결 도중 어려웠던 점

최초 문제 접근시 입력 숫자가 주어지고 1로 만들기 위한 연산 횟수를 구하는 것 까지는 풀었지만, 연산 횟수 중 최솟값을 출력해야하는 점에서 해결하지 못하였다.(위 문제 예시에서 숫자 '10'의 경우가 그러하다.)

10 -> 5 -> 4 -> 2 -> 1 (연산횟수 총 4회)

10 -> 9 -> 3 ->1           (연산횟수 총 3회)

package 백준알고리즘;
import java.util.Scanner;
public class Q1463 {
    public static void main(String[] args) {

        //1. 입력값
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();

        int calcX = X;
        int calcNum = 0;
        while(calcX != 1){
            if (calcX % 3 == 0) {
                calcX = calcX/3;
            }else if (calcX % 2 == 0) {
                calcX = calcX/2;
            }else{
                calcX -= 1;
            }
            calcNum++;
            System.out.println("[FIRST]calcX:[" + calcX + "]");
            System.out.println("[FIRST]calcNum:[" + calcNum + "]");
        }
        sc.close();
    }
}

위 작성코드는 필자가 최초에 문제를 접하고 풀이했던 코드이다.

풀이과정은 아래와 같다.

1. 연산횟수를 계산할 타깃 숫자 X를 입력받는다.

2. 최초 X를 임의의 변수 calcX에 대입한다.

3.  calcX가 3의 배수인지 체크 아닐경우 2의 배수인지 체크 아닐 경우 -1 의 순으로 연산을 처리한다.

여기서부터, 필자의 경우 큰 수부터 체크를 하면 작은 연산 횟수가 나오지 않을 까 지레짐작 하였지만, 문제 예시 중 '10' 연산 횟수만 보아도 최소연산횟수를 구할 때 최초, 10-1부터 수행을 하였으니 접근법이 잘못되었음을 인지는 하였으나, 어떻게 접근해야 할지 전혀 감이 잡히지 않았다.

 

문제해결방법

위 알고리즘 문제를 해결할 방법이 감이 잡히지 않아 검색을 해보니 해당 문제는 다이나믹 프로그래밍(dp)을 다루는 유형임을 알게되었고, 다이나믹 프로그래밍에는 두 가지 방식이 있었는데, TopDown 방식과 BottomUp방식이 존재하였다. 

아래는 BottomUp방식의 풀이다.

package 백준알고리즘;
import java.util.Scanner;
public class Q1463_재시도 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 3 == 0) {
                System.out.println("3일떄->dp["+i+"]::"+dp[i] +", dp["+i+"/3]+1::"+dp[i/3]+1);
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
            if (i % 2== 0) {
                System.out.println("2일때->dp["+i+"]::"+dp[i] +", dp["+i+"/2]+1::"+dp[i/2]+1);
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            System.out.println("dp["+i+"]::"+dp[i]);
            System.out.println("====================");
        }
        System.out.println("최종::"+dp[n]);
        sc.close();
    }
}

      

 

 

 

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

해결방법 참고 : https://odysseyj.tistory.com/19

[알고리즘-JAVA] 백준 알고리즘 1463번 - 1로 만들기