DP #1463: 1로 만들기 [JAVA]
https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
[ 참조 블로그 ] https://st-lab.tistory.com/133
접근 방법
10을 예로 들어보자.
10에 연산1,2,3을 적용하여 1을 만드는 최소 연산 횟수를 구해야한다.
10은 2로 나누거나 1을 뺄 수 있다.(1회 연산)
1. 2로 나눈다. 5가 됨 -> 5에 연산1,2,3 적용해서 1 만드는 최소 연산 횟수를 알아야.
2. 1을 뺀다. 9가 됨 -> 9에 연산1,2,3 적용해서 1 만드는 최소 연산 횟수를 알아야. (문제 힌트에서 10이 1로 갈 때 9를 거침.)
즉, '10이 1로 가기위한 최소한의 연산 횟수를 구하는 문제'는 '9가 1로 가기위한 최소한의 연산 횟수'를 구하는 문제로 바뀜
dp[i]에 저장된 값 > i에 연산1,2,3을 적용해서 1을 만드는 최소 연산 횟수
주어진 연산들을 할 수 있는 경우를 다음과 같이 나누어야 함.
6으로 나뉜다. -> -1, /2, /3 가능
3으로 나뉜다. -> -1, /3 가능
2로 나뉜다. -> -1, /2가능
else. -> -1 가능
코드
top down - 재귀
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Integer dp[];
public static void main(String[] args) throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(bf.readLine());
dp=new Integer[n+1];
dp[0]=dp[1]=0;
System.out.println(recur(n));
bf.close();
}
static int recur(int n) {
if(dp[n]==null) {
if(n%6==0) {
dp[n]=Math.min(recur(n-1), Math.min(recur(n/3),recur(n/2)))+1;
}
else if(n%3==0) {
dp[n]=Math.min(recur(n/3), recur(n-1))+1;
}
else if(n%2==0) {
dp[n]=Math.min(recur(n/2), recur(n-1))+1;
}
else {
dp[n]=recur(n-1)+1;
}
}
return dp[n];
}
}
bottom up - 반복문
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static Integer dp[];
public static void main(String[] args) throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(bf.readLine());
dp=new Integer[n+1];
dp[0]=dp[1]=0;
for(int i=2;i<=n;i++) {
if(i%6==0) {
dp[i]=Math.min(dp[i-1], Math.min(dp[i/3],dp[i/2]))+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.println(dp[n]);
bf.close();
}
}
▲ 참고 및 주의사항
1. 메모제이션할 배열을 int로 선언하지 않고 Integer로 선언한 이유
-> int로 선언하면 모든 배열 요소가 0으로 초기화되는데 애초에 dp[0]과 dp[1]은 계산 결과값이 0이기 때문에
방문하지 않은 요소의 검사를 위해서 나머지 요소들을 -1과 같은 값으로 다시 초기화 해줘야함. Integer로 하면 초기화해줄 필요 없이 null로 방문 여부 검사 가능.
2. recur부르는 연산의 순서
N-1부터 호출하면 시간 초과될 수 있는데 N-1부터 호출하게 되면 어떤 경우든 0부터 N-1까지 모두 탐색되기 때문. 그러니 N/3, N/2 같이 일정 부분만 먼저 탐색해서 메모이제이션을 하고, 만약 그 뒤에 N-1이 호출되더라도 N/3 혹은 N/2 에서 이미 탐색했던 값이라면 반환되도록 하는 것이 탐색이 훨씬 덜 걸린다.