[백준] 1463번 1로 만들기 JAVA (자바) 풀이
문제 1463번
: 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지
- X가 3으로 나누어 떨어지면, ÷ 3
- X가 2로 나누어 떨어지면, ÷ 2
- - 1
위와 같은 연산 세 개를 사용해서 N = 1을 만들려고 할 때 연산의 최소 횟수를 출력
[입력]
: 첫 줄에 N (1 ≤ N ≤ 106)
[출력]
: 첫째 줄에 연산을 하는 횟수의 최솟값을 출력
[설명]
DP 알고리즘
: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법
DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다
1) Top-down(하향식)
하위 문제를 재귀적으로 호출하여 해결함으로서 상위 문제를 해결하는 방식
이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization사용
public class Topdown {
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
// Top-down
static int fibo(int x) {
if( x ==1 || x==2) return 1;
if(dp[x] != 0) return dp[x];
dp[x] = fibo(x-1) + fibo(x-2);
return dp[x];
}
}
2) Bottom-up(상향식)
하위에서부터 문제를 먼저 해결하고 얻어진 값들을 이용해서 상위 문제를 해결해나가는 방식
반복문을 사용해서 구현하고 문제의 결과 값을 저장하는 리스트는 DP 테이블이라 부른다
public class Bottomup {
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
// Bottom-up
static int fibo(int x) {
dp[1] =1;
dp[2] =1;
for(int i=3; i<x+1; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[x];
}
[문제 설명]
- 2와 3은 직관적으로 판단 가능하다
둘 다 연산 횟수는 1이다 - 여러 연산이 가능하지만 편의상 하나씩만 썼다
( 예를 들면 <4> 연산방법으로 ÷ 2 - 1 해도 된다 ) - 연산 규칙은 무조건 세 가지 해보고 제일 작은거 고르면 된다
세가지: ÷ 3해보고 ÷ 2해보고 - 1해보고 나온 index값의 연산횟수에서 +1 만 해준다 - 참고영상
[예시1]
index <6> 라면
1. ÷ 3해서 나온 index값 + 1
÷ 3해서 나온 index는 <2>이다
우리는 위에서 index <2>의 연산 횟수를 미리
구해놓았다 ( <2> 연산 횟수 = 1 )
여기서 + 1 해주면 되는데, 왜 +1을 해주냐면
우리가 ÷ 3 해서 나온 값이기 때문에 그연산까지
합쳐서 횟수로 포함하므로 + 1
즉 <6>의 연산 횟수는 2이다
2. ÷ 2해서 나온 index값 + 1
÷ 2해서 나온 index는 <3>이다
<3>의 연산횟수는 1이고 + 1을 더해주면
<6>의 연산 횟수는 2이다
3. -1해서 나온 index값 + 1
-1해서 나온 index는 <5>이다
<5>의 연산횟수는 3이고 + 1을 더해주면
<6>의 연산횟수는 4이다
1,2,3번 중 가장 최소값은 2이다
[탑다운 코드]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[1000001]; //DP 배열 초기화
dp[2] = 1;
dp[3] = 1;
for (int i = 4; i <= n; i++) {
if (i % 6 == 0) {
dp[i] = Math.min(dp[i/3], Math.min(dp[i/2], dp[i-1])) + 1;
} else if (i % 3 == 0) {
dp[i] = Math.min(dp[i/3], dp[i-1])+1;
} else if (i % 2 == 0) {
dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;
} else {
dp[i] = dp[i-1] + 1;
}
}
System.out.print(dp[n]);
}
}
[해설]
: int n = Integer.parseInt(br.readLine()); 첫째줄 입력받기
: int[] dp = new int[1000001]; DP 배열 초기화
: dp[2] = 1; 2는 쉽게 파악 가능해서 초기화
dp[3] = 1; 3도 쉽게 파악 가능해서 초기화
: for (int i = 4; i <= n; i++) { 3까지 초기값 설정했으니 4부터 판단 시작
if (i % 6 == 0) { 3과 2 둘 다 나누어 떨어질 때
dp[i] = Math.min(dp[i/3], Math.min(dp[i/2], dp[i-1])) + 1; 가장 최소값에서 + 1
}
else if (i % 3 == 0) { 3으로만 나누어 떨어질 때
dp[i] = Math.min(dp[i/3], dp[i-1])+1; 가장 최소값에서 +1
}
else if (i % 2 == 0) { 2로만 나누어 떨어질 때
dp[i] = Math.min(dp[i/2], dp[i-1]) + 1; 가장 최소값에서 +1
}
else { 3과 2 둘다 나누어 떨어지지 않을 때
dp[i] = dp[i-1] + 1; -1 연산 밖에 없음 그 값에서 + 1
}
}
: System.out.print(dp[n]); 해당 dp 값 출력
[보텀업 코드]
import java.util.Scanner;
import java.lang.Math;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] dp = new int[N+1];
dp[1] = 0;
for(int i=2; i<= N; i++) {
dp[i] = dp[i-1] + 1;
if(i % 2 == 0){
dp[i] = Math.min(dp[i], dp[i/2] + 1);
}
if(i % 3 == 0) {
dp[i] = Math.min(dp[i], dp[i/3] + 1);
}
}
System.out.print(dp[N]);
}
}
[해설]
: int N = sc.nextInt(); 첫째줄 입력
: int[] dp = new int[N+1]; dp 생성
dp[1] = 0; dp[1] 값 초기화
: for(int i=2; i<= N; i++) { 2부터 시작
dp[i] = dp[i-1] + 1; 바로 전의 index 값을 확인하기 위해 -1 연산부터 시작
if(i % 2 == 0){ 만약 2로 나눠 떨어지면
dp[i] = Math.min(dp[i], dp[i/2] + 1); -1이나 ÷2 중에 더 작은 값 구하기
}
if(i % 3 == 0) { 만약 3으로 나눠 떨어지면
dp[i] = Math.min(dp[i], dp[i/3] + 1); -1이나 ÷3 중에 더 작은 값 구하기
}
}
: System.out.print(dp[N]); 출력
이제 풀어보러 갈께요 :)
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *