[ 백준 - 1463 ] 1로 만들기

난이도 : S3

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

Tag : DP

 

문제 탐색하기 

- 특정 숫자를 1로 만드는 가장 적은 횟수를 출력한다.

- 3으로 나누기, 2로 나누기, 1빼기가 가능하다.

1빼기가 있기 때문에 무조건 1로 만들기가 가능하다.

 

시도 1 ( 성공😲)

떠오른 문제 해결 방법

 

DP문제는 점화식을 만드는게 중요하기 때문에 일단 난이도가 쉬운 문제를 접근하였습니다.

DP에서는 배열을 잡는 것이 중요합니다.

이번 문제에서는 배열을 count[i]=1로만드는 가장 적은 횟수로 하였습니다.

그렇게 되면 다음과 같은 관계를 나타낼수 있습니다.

count[1] = 0  //이미 1

count[2] = 1 //

...

count[i]=min( count[i/3]+1, count[i/2] + 1,  count[i-1] + 1)

즉, 3으로 나눴을때, 2로 나눴을 때, 1로 나눴을때 가장 적은 횟수에 +1한것이 현재 i를 1로만드는 가장 적은 횟수입니다.

시간복잡도⏰

count[2]부터 count[n] 까지 반복하면 되기 대문에 O(n), 1,000,000 으로 0.15초안에 해결이 가능합니다.

구현 방법 

세부 구현 사항

1. 주어진 값을 입력받는다. ( 최대 4만개를 입력받기 때문에 BufferedReader활용)

2. count[1] = 0으로 초기화한다.

3. 선택지 3개중 가장 적은 횟수를 count[i]에 저장한다. i는2부터 n까지 반복한다.

4. count[n]을 출력한다.

 

전체코드

import java.io.IOException;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] count = new int[n + 1];
        count[1] = 0;
        for (int i = 2; i <= n; i++) {
            int minValue = count[i - 1] + 1;

            if (i % 3 == 0) {
                minValue = Math.min(minValue, count[i / 3] + 1);
            }
            if (i % 2 == 0) {
                minValue = Math.min(minValue, count[i / 2] + 1);
            }
            count[i] = minValue;
        }
        System.out.println(count[n]);
    }
}

 

 

마무리

DP는 코딩테스트에도 많이 나오기 때문에 점화식, 배열을 어떻게 할것인가에 집중하여 많은 연습이 필요할 것 같습니다.