[DP] 백준 실버3 1463번 1로 만들기

문제

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

정답

정답은 더보기

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

public class Main {

    private static int[] array = new int[1000003];

    public static void main(String[] args) throws Exception {
        // array[1] = 0;
        array[2] = 1;
        array[3] = 1;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());

        for (int i = 4; i < array.length; i++) {
            int a = Integer.MAX_VALUE;  // 만약, i를 3으로 나눌 수 있는경우 -> 3으로 나눈 값을 저장할 변수
            int b = Integer.MAX_VALUE;  // 만약, i를 2으로 나눌 수 있는경우 -> 2으로 나눈 값을 저장할 변수
            int c = Integer.MAX_VALUE;  // i에서 1을 뺀 값을 저장할 변수

            if (i % 3 == 0) {
                a = array[i / 3];       // array[i/3]에는 n(i)을 1로 만들때의 최솟값이 있음
            }
            if (i % 2 == 0) {
                b = array[i / 2];       // array[i/2]에는 n(i)을 1로 만들때의 최솟값이 있음
            }
            c = array[i - 1];           // array[i-1]에는 n(i)을 1로 만들때의 최솟값이 있음

            array[i] = Math.min(a,Math.min(b,c)) + 1;
        }

        System.out.println(array[input]);

    }

}

 

풀이

• 우선, 무식하게 경우의 수를 하나하나 다 따져보았다.
• 문제에서 나오는 연산 세가지 방식을 아래 a,b,c로 대신 표기하겠다.

• N = 1이면 이미 1이기 때문에 1이 되기 위한 최솟값은 0번이고
• N = 2이면 1이 되기 위한 방법은 두 가지다. b 아니면 c, 어쨋든 둘 중 어느것을 하던 1번만 연산하면 1이되므로 최솟값은 1번이다.
• 이제부턴 N = 3, N = 4인 경우는 아래 그림을 참고
• N을 1로 만들기 위한 최소한의 연산 횟수를 N = 숫자 : 총 _번 이라고 표현 했다.

N = 3인 경우

 

• N = 3일 경우를 보면 우선 a와 c방식을 사용해서 각각 연산이 가능하다. 단, c방식의 경우 결과가 2가 되기 때문에 1로 만들기 위해선 한 번 더 연산해야하기 때문에 N = 3인 경우 처음부터 a방식을 사용해 1로 만드는 총 1번이 제일 작은 최솟값이다.

N = 4인경우

• N = 4인 경우도 마찬가지로 위의 방식대로 해보면 1로 만들 수 있는 가장 작은 횟수는 2번이다.

위의 풀이를 하다보면 살짝 무언가 느낌이 오는게 있는가??

그렇다면 직접 찾아보거나 아니면 N이 5이거나 6일 때까지 한 번 시도해보자.

 

이제 내가 접근했던 방식을 말해보자면

N을 하나씩 증가시키면서 최솟값을 찾다보면 이전에 계산했었던 숫자들을 다시 계산하는 일이 반복된다.

어차피 N = 2 일때 최솟값은 1, N = 3 일때 최솟값은 1, N = 4일때 최솟값은 2 인 것처럼 말이다.

 

그래서 차라리 배열에다가 처음 조건만으로도 알 수 있는 N = 1,2,3 일 때의 최솟값은 미리 저장해두고

 

그 이후의 N부터는 

1. a,b,c 방식이 가능한 경우를 따져보고(연산 1한번)

2. 가능한 방식을 통해 연산한 결과는 이미 배열에 저장되어 있으므로 배열[연산한 결과]의 값을 가져와서

3. 1번과 2번을 더하게 되면 N일 때의 최솟값이 결정된다.

 

결론

 

코딩테스트를 준비하면서 처음 풀어보는 DP문제였는데 물론 30분 안에 풀지 못했다.

그래서 유튜브에서 여러가지 해설을 본 다음, 문제를 이해하고 풀이방법들을 이해해보니 어떤 식으로 접근해야될 지 감이 왔다.

일단 현재 단계에서는 직접 손으로 그려가면서 따져보자!