[BOJ/JAVA] 백준 1463 : 1로 만들기 (자바)

문제 정보

  문제명   - 1로 만들기
  난이도   - 실버 III
문제 번호 - 1463번

---

문제 링크

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

1463번: 1로 만들기

---

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
 2. X가 2로 나누어 떨어지면, 2로 나눈다.
 3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

---

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
2	1
10	3

---

알고리즘 분류

● 다이나믹 프로그래밍

---

소스코드

package Lv2_Silver;

import java.io.*;
/**
 * @author HanHoon
 * @category 다이나믹 프로그래밍
 * https://www.acmicpc.net/problem/1463
 */
public class BOJ_S3_1463_1로_만들기 {
	/**
	 * 시간 비교
	 * 1. 재귀 O, Math O: 시간 초과
	 * 2. 재귀 O, Math X: 236ms
	 * 3. 재귀 X, Math O: 104mx
	 * 4. 재귀 X, Math X: 104ms
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		// 연산 횟수 저장
		int[] dp = new int[N+1];

		dp[0] = dp[1] = 0;

		for(int i = 2; i <= N; i++){
			dp[i] = dp[i-1] + 1;

			// 2번 연산
			if(i%2==0)
				dp[i] = Math.min(dp[i], dp[i/2]+1);

			// 1번 연산
			if(i%3 == 0)
				dp[i] = Math.min(dp[i], dp[i/3]+1);
		}

		System.out.println(dp[N]);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---