BOJ(백준 온라인 저지) 1463번 with 자바[JAVA]

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

1463번: 1로 만들기

---

DP 를 안다면 풀 수 있는 문제였다.

DP 의 핵심은 이전에 계산했던 것을 다시 활용하는 것이다.

 

처음에는 DP를 생각하지 못했다. N 의 크기 때문에 N 이 주어졌을 때 가능한 모든 경우의 수를 계산 해보는 식의 방법은 안될 것 같다고 생각했고, 그러면 일종의 알고리즘을 만들어서 해결해봐야겠다고 생각했다.

 

문제를 보자

임의의 정수 X에 대해 X가 1이 되도록 만드는 최소 횟수를 찾는것이다.

 

처음에는 간단하게 생각했다. 어떤 수가 나오든 대응할 수 있는 로직을 생각해봤다. 이를 바탕으로 연산의 우선순위를 생각해 보았는데...

 

 

• 3으로 나눌 수 있다면 3으로 나누기

2로 나누는 연산이나 -1을 하는 연산은 X가 1로 다가가는 방법이긴 하지만 3으로 나누는것이 비해 느린것이 자명하다. 그래서 3으로 나눌 수 있다면 3으로 먼저 나누는 것이 1순위라고 생각했다.

 

 

 

• 2로 나눌 수 있다면 2로 나누기

3으로 나누는 연산은 모두 수행해서 더 이상 3으로 나눌 수 없거나, 애초에 N 이 3의 배수가 아닌 경우, -1 연산 보다 2로 나누는 연산이 1로 다가가는 더 빠른 방법이기에 2순위로 생각했다.

 

 

 

• 위에 두 개가 안되는 경우(2의 배수도 아니고 3의 배수도 아닌 경우) 에는 -1을 한다.

위에 두 연산이 불가하다면 -1 연산 밖에 할게 없다.

 

 

 

 

위에 알고리즘을 바탕으로 N 이 10 이 주어진 경우를 보자

 

1. 3으로 나눌 수 없으니 1번은 패스

2. 2로 나눌 수 있으니 나누기 2 연산을 수행한다.(N=5)

3. 5는 3, 2 의 배수가 아니니 -1 연산을 수행한다.(N=4)

4. 4는 2의 배수이니 나누기 2 연산을 수행한다(N=2)

5. 2는 2의 배수이니 나누기 2 연산을 수행한다(N=1)

 

따라서 4가 출력이 된다.

하지만 정답은 3이다.

 

1. -1 연산을 한다(N=9)

2. 9는 3의 배수이니 나누기 3 연산을 수행한다.(N=3)

3. 3은 3의 배수이니 나누기 3 연산을 수행한다.(N=1)

 

따라서 3이 출력된다.

 

이때 "N이 주어졌을 때 -1 연산을 수행하거나 /2, /3 연산을 수행하는 기준이 뭐지?" 라고 생각했다.

 

 

 

 

다시 생각해보니 보였다.

 

N=10 으로 주어졌을 때 N 에 대해 할 수 있는 연산은 3가지 밖에 없다(/3, /2, -1). 그리고 N 에 대해 3가지 연산을 한 수를 M 이라 한다면 F(N) = F(M) + 1 이다. (* 이때 F(x) 는 x가 1에 다가가기 위한 최소 연산 횟수, 즉 문제의 정답이다)

 

왜냐하면 F(M) 의 경우 M에서 1까지 다가가기 위한 최소 횟수이고, 우리는 이를 이용하여 F(N) 을 찾을 수 있다. 굳이 3가지 연산을 섞어가면서 1까지 "직접" 다가가지 말고 이전 연산의 결과를 이용할 수 있다는 것이다.

 

문제는 이제 쉬워졌다. 

N 에서 M 이 되는 3가지 경우에 수에 대해 F(M) 들을 비교하여 가장 작을 값을 찾아 +1 을 해주면 된다.

 

코드를 보자.

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

public class Main {
    public static void main(String[] args) throws IOException
    {
        int[] list = new int[1000001]; // 10e6 경우의 수의 정답을 담을 list

        list[1] = 0; // index 에서 출발했을때의 거리
        list[2] = 1; // /2 하면 바로 1
        list[3] = 1; // /3 하면 바로 1

        for(int i=4; i<1000001; i++) {
            int path;

            path = list[i - 1] + 1;

            if (i % 3 == 0)
                if (path >= list[i / 3] + 1)
                    path = list[i / 3] + 1;

            if (i % 2 == 0)
                if (path >= list[i / 2] + 1)
                    path = list[i / 2] + 1;

            list[i] = path;
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        System.out.println(list[N]);
    }
}

 

---

• 느낀 점

이전의 연산을 다음 연산에 활용하는 DP 의 개념을 확실히 알게 되었다.

Recursion 을 사용해도 가능할 것 같은데 N의 수가 너무 커서 시간 초과가 날 수 있을 것 같다.