알고리즘/BOJ - Java
[BOJ/Java] 1463. 1로 만들기
ImJay
2024. 4. 23. 09:39
반응형
[BOJ/Java] 1463. 1로 만들기
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
문제 해석
이 문제는 주어진 수 N을 1로 만드는 최소 횟수를 구하는 문제다. 수행할 수 있는 연산은 세 가지로, N을 3으로 나누기, 2로 나누기, 또는 1을 빼는 연산이 있다. 주어진 N에 대해 세 가지 연산을 적절히 조합하여 1로 만드는 데 필요한 최소 연산 횟수를 찾는 것이 목표다.
풀이 과정
본 코드는 동적 계획법을 사용하여 문제를 해결한다. 배열 dp를 사용하여 각 숫자 i를 1로 만들기 위해 필요한 최소 연산 횟수를 저장한다. dp[i]는 i번째 숫자를 1로 만드는 데 필요한 최소 연산 횟수를 나타낸다.
- 초기화: dp[1]은 0으로 설정한다. 1을 1로 만드는 데 필요한 연산은 없으므로 연산 횟수는 0이다.
- 점화식 구성: 각 숫자 i에 대해, i가 1인 경우를 제외하고, 다음의 점화식을 사용한다:
- dp[i] = dp[i-1] + 1: i에서 1을 빼는 연산.
- if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1): i가 3으로 나누어떨어질 경우, i를 3으로 나누는 연산.
- if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1): i가 2로 나누어떨어질 경우, i를 2로 나누는 연산.
- 위 점화식을 사용하여, 각 i에 대해 세 가지 연산 중 최소값을 dp[i]에 저장한다.
- 결과 출력: 계산된 dp[N]을 출력하여 주어진 N을 1로 만드는 데 필요한 최소 연산 횟수를 제시한다.
코드
package edu.ssafy.im.BOJ.Silver.S3.No1463.second;
import java.io.*;
public class Main {
private static int N;
private static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine()); // 입력 받은 수 N
dp = new int[N + 1]; // N+1 크기의 배열 생성
dp[1] = 0; // 1은 이미 1이므로 연산 필요 없음
for (int i = 2; i <= N; i++) {
dp[i] = dp[i-1] + 1; // 1을 빼는 연산
if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1); // 3으로 나누는 연산
if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1); // 2로 나누는 연산
}
sb.append(dp[N]); // 결과 값 StringBuilder에 추가
bw.write(sb.toString()); // 결과 값 출력
bw.flush();
bw.close();
}
}
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N)이다. 각 숫자 i에 대해 세 가지 경우의 수를 확인하고 최소값을 구하는 연산을 수행한다. 그러나 각 i에 대해 일정한 수의 연산만 수행되므로, 시간 복잡도는 입력 크기 N에 선형적으로 비례한다.
느낀점
동적 계획법을 통해 복잡한 문제를 단순화시켜 해결할 수 있었다는 점이 매우 인상적이었다. 문제를 작은 단위로 나누어 각 단위의 최적해를 찾는 방식이 강력함을 다시 한번 느낄 수 있었다. 이러한 접근 방식은 다양한 최적화 문제에 활용 가능하여 알고리즘 설계에 있어 매우 중요한 기술이다.
반응형