[BOJ] 1463 - 1로 만들기

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

난이도: 실버 3

사용언어: JAVA

 

풀이

문제의 시간제한을 봐도 알 수 있듯이, 이 문제는 다이나믹 프로그래밍을 이용해서 해결해야 합니다. 문제는 1을 만드는 것이지만, 구현은 반대로 1에서 N을 만드는 최소 연산 수를 구하는 식으로 했습니다. 

 

배열을 하나 만들어, 반복문을 돌며 배열의 i 번째 칸에 i까지 오는데 걸리는 연산의 최소 횟수를 저장해주고, 마지막에 배열의 N번째 칸에 들어있는 값을 출력해주면 됩니다.

 

i 번째 칸까지 오는데 필요한 연산의 최소 횟수는,

(1). i-1 까지 오는데 필요한 연산의 최소 횟수 +1 or

(2). i/2 까지 오는데 필요한 연산의 최소 횟수 +1 or

(3). i/3 까지 오는데 필요한 연산의 최소 횟수 +1

(물론 2, 3번은 각각 2와 3으로 나눌 수 있는 경우에만 고려)

세 가지 경우 중 최솟값과 같습니다.

 

1을 만드는 것이 목표이기 때문에, 배열의 1번 칸은 0으로 시작하고, 2번 칸부터 채워 넣으면 됩니다.

 

import java.io.*;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int []arr = new int[N+1];
        int i;
 
        for(i=2;i<=N;i++){
            arr[i] = arr[i-1]+1; // (1)
            if(i%2 == 0) // 2로 나누어 지는 경우. (2)
                arr[i] = Math.min(arr[i],arr[i/2]+1);
            if(i%3 == 0) // 3으로 나누어 지는 경우. (3)
                arr[i] = Math.min(arr[i],arr[i/3]+1);
        }
        bw.write(String.valueOf(arr[N]));
        bw.flush();
    }
}