728x90
https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 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]);
}
}
반응형
'코딩 문제 풀기 ( Algorithm problem solving ) > 백준 온라인 저지 ( BOJ )' 카테고리의 다른 글
[백준(Baekjoon)][자바(java)] 2156 : 포도주 시식 / 동적 계획법 1 (0) | 2020.06.19 |
---|---|
[백준(Baekjoon)][자바(java)] 10844 : 쉬운 계단 수 / 동적 계획법 1 (0) | 2020.06.19 |
[백준(Baekjoon)][자바(java)] 2579 : 계단 오르기 / 동적 계획법 1 (0) | 2020.06.19 |
[백준(Baekjoon)][자바(java)] 1932 : 정수 삼각형 / 동적 계획법 1 (0) | 2020.06.19 |
[백준(Baekjoon)][자바(java)] 1149 : RGB거리 / 동적 계획법 1 (0) | 2020.06.19 |