[백준 알고리즘] 백준 1463번 1로 만들기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1463번 1로 만들기 자바(Java)

1) 문제번호 : 1463번

 

2) 문제 출처

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

2. 문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

3. 제약사항

- 

4. 입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

5. 출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

6. 풀이

- dp에서 0과 1일 때는 0이 되니까 dp[0]과 dp[1]의 값은 0으로 넣는다.

- dp[2]는 dp[1]+1을 하면 된다.

- dp[3]일 경우에는 dp[1]+1을 하면 된다.

- dp[4]일 경우에는 2로 2번 나누면 된다. 그렇기에 연산 수는 2번이 되고, dp[2] + 1을 하면 된다.

- 이 규칙으로 다른 것도 진행하면 된다.

 

7. 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
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[N+1];
		dp[0] = 0;
		dp[1] = 0;
		
		for(int i=2;i<=N;i++) {
			dp[i] = dp[i-1]+1;
			
			if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3]+1);
			if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2]+1);
		}	
        
		System.out.println(dp[N]);
	}
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
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[N+1];
		dp[0] = 0;
		dp[1] = 0;
		
		for(int i=2;i<=N;i++) {
			int minus;
			int two = Integer.MAX_VALUE;
			int three = Integer.MAX_VALUE;
			
			if(i%3==0) three = dp[i/3]+1;
			if(i%2==0) two = dp[i/2]+1;
			
			minus = dp[i-1]+1;
			
			int result = Math.min(Math.min(two, three), minus);
			
			dp[i] = result;
		}
		System.out.println(dp[N]);
	}
}

---