[백준/DP] 1463번 1로 만들기 (JAVA)
문제
풀이
8달 전에 풀었다가 실패하고 버린 문제 같은데... 왜 버렸지..? 지금은 한 번에 풀었는데 어쨌든 기분은 좋다 ㅎㅎ;;
- 4부터 n까지 차례로 탐색하며 아래 세 가지 경우를 고려한다. 나누기와 빼기가 같이 있어서 어떤 것이 최솟값일지 보장할 수 없기 때문에 모두 고려해야 한다.
i
가 3으로 나눠지면 최솟값과dp[i/3]
를 비교하고 갱신i
가 2로 나눠지면 최솟값과dp[i/2]
를 비교하고 갱신- 최솟값과
dp[i-1]
를 비교하고 갱신- 위 세 가지 경우 중 최솟값에 연산횟수 1을 더하고
dp[i]
에 저장한다.
코드
import java.io.*;
public class Main {
private static final int MAXIMUM = 1000000;
private static int n;
private static int[] dp = new int[MAXIMUM + 1];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
dp();
bw.append(Integer.toString(dp[n]));
br.close();
bw.close();
}
private static void dp() {
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for (int i = 4; i <= n; i++) {
int min = Integer.MAX_VALUE;
if (i % 3 == 0) min = Math.min(min, dp[i / 3]);
if (i % 2 == 0) min = Math.min(min, dp[i / 2]);
min = Math.min(min, dp[i - 1]);
dp[i] = min + 1;
}
}
}
Author And Source
이 문제에 관하여([백준/DP] 1463번 1로 만들기 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jwkim/dp-1463저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)