[백준] no1463: 1로 만들기

문제

다음의 세 가지 연산만 가능 할 때, 주어진 숫자 X를 1로 만드는 최소한의 연산수를 구해라

 

1. 3으로 나누어 떨어지면, 3으로 나누기가 가능하다

2. 2로 나누어 떨어지면, 2로 나누기가 가능하다

3. 1을 뺀다

 

문제 링크: https://www.acmicpc.net/problem/1463

---

원리

1. 무조건 큰 수로 나눈다고 연산이 제일 적어지는 것이 아니다.

2. 2와 3 모두 나눌 수 있는 경우는 6으로 나눌 수 있는 경우다.

---

풀이방법

1. DP

2. 재귀

---

나의 코드

1. 일반 반복 - [실패]

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class no1463 {

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

        int X = Integer.parseInt(br.readLine());

        int count = 0;
        while (X>1) {
            if (X%6==0) {
                X/=6;
                count+=2;
            } else if ((X - 1) % 6 == 0) {
                X--;
                count++;
            } else if((X-1)%3==0) {
                X--;
                count++;
            }
            else if(X%3==0) {
                X/=3;
                count++;
            }
            else if ((X-1)%2==0) {
                X--;
                count++;
            }
            else if (X%2==0) {
                X/=2;
                count++;
            }
            else {
                X--;
                count++;
            }

        }
        System.out.println(count);
    }
}

 

2. DP

static Integer[] dp;

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

    int X = Integer.parseInt(br.readLine());
    // Integer배열인 이유는 길이 설정시, 모든 자리에 null로 채워지기 때문. X+1사이즈를 해야 인덱스에 맞게 들어간다.
    dp = new Integer[X+1];
    // 0 또는 1일경우, null이 아니어야 재귀반복이 종료된다. 초기화 시켜놓지 않으면, -1까지 가서 OutOfIndex 발생
    dp[0] = dp[1] = 0;

    System.out.println(recur(X));

}

private static int recur (int X) {
    // 0 또는 1에서 0을 만나기 전까지 재귀 반복함
    if(dp[X]==null) {

        // 6으로 나눠지는 경우
        // 3으로 나눈 경우와 2로 나눈 경우 중 최소값 => 앞에서 구한 최소값과 -1했을 때의 최소값 중 최소값 => 최종 결과에 +1 한 값
        if(X%6==0) dp[X] = Math.min(recur(X-1) , Math.min(recur(X/3) , recur(X/2) )) + 1;

        // 3으로만 나눠지는 경우
        else if (X%3==0) dp[X] = Math.min(recur(X/3), recur(X-1)) + 1;

        // 2로만 나눠지는 경우
        else if (X%2==0) dp[X] = Math.min(recur(X/2), recur(X-1)) + 1;

        // 2와 3 모두 안되는 경우
        else dp[X] =recur(X-1) + 1;
    }

    return dp[X];
}

 

 

---

레퍼런스 코드

DP 및 재귀 방식

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