백준 - 1463번(1로 만들기)
문제 출처: https://www.acmicpc.net/problem/1463
문제
-
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
-
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
int[] DP = new int[N + 1]; // DP 테이블
for (int i = 2; i <= N; i++) {
int min = 1 + DP[i - 1];
if (i % 3 == 0 && 1 + DP[i / 3] < min) min = 1 + DP[i / 3];
if (i % 2 == 0 && 1 + DP[i / 2] < min) min = 1 + DP[i / 2];
DP[i] = min;
}
System.out.println(DP[N]);
}
}
- DP를 사용하여 풀 수 있는 문제였다.
- 각각의 단계에서 1을 뺐을 때의 연산 수, 3으로 나누어지는 경우 3으로 나눈 때의 연산 수, 2로 나누어지는 경우 2로 나눈 때의 연산 수 중 최솟값을 DP 테이블에 저장하여 진행하였다.
Author And Source
이 문제에 관하여(백준 - 1463번(1로 만들기)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ghc1124/백준-1463번1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)