[백준(Baekjoon)][자바(java)]1463 : 1로 만들기 / 동적 계획법 1

728x90

 

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

 

1463번: 1로 만들기

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

www.acmicpc.net

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X3으로 나누어 떨어지면, 3으로 나눈다.

2. X2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

정수 N이 주어졌을 때위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

풀이 방법

-  N에 대해 1을 만들 수 있는 연산의 최소 횟수를 담을 dp배열 생성

-  연산은 3가지임 ( -1, / 2, / 3 )

-  상향식으로 2부터 N까지 연산의 최소 횟수 값을 더해나가는데,
   N
에서 3가지 연산을 한 후 그 중 작은 값에 +1 한 값이 dp[N]의 값
 ( 3가지 연산을 한 값을 각각 비교할 때, '/ 2'와 '/ 3'의 경우 나누어떨어지지 않으면 MAX_VALUE을 대입함 )

 

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

public class Main {

	public static void main(String[] args) throws Exception {

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

		int dp[] = new int[n + 1],	// cnt, num
			c1, c2, c3, 				// calculate
			num;
		for (num = 2; num <= n; num++) {
			c1 = dp[num - 1];
			c2 = num % 2 == 0 ? dp[num / 2] : n;
			c3 = num % 3 == 0 ? dp[num / 3] : n;
			dp[num] = Math.min(c1, Math.min(c2, c3)) + 1;
		}
		
		System.out.println(dp[n]);
	}
}

 

 

반응형