백준 1463번 : 1로 만들기

 문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

1463 1로 만들기

 

 구현 방법

 dp로 풀어주었습니다. 1부터 시작하여 횟수의 최솟값을 구해주었습니다.

모든 값이 할 수 있는 연산인 -1을 dp 에 넣고 /2가 가능하면 /2의 값과 현재 -1을 한 dp 값을 비교하여 더 작은 값을 dp에 넣어줍니다. /3도 마찬가지로 비교하여 더 작은 값을 dp에 넣어줍니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ1463_1로만들기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N + 1];
        for(int i = 2; i <= N; i++){
            arr[i] = arr[i - 1] + 1;
            if(i % 2 == 0) arr[i] = Math.min(arr[i], arr[i / 2] + 1);
            if(i % 3 == 0) arr[i] = Math.min(arr[i], arr[i / 3] + 1);
        }
        System.out.println(arr[N]);
	}
}

 

정답!