Baekjoon1463*: 1로 만들기

1로 만들기

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.15 초 (하단 참고)

128 MB

169868

54512

34481

31.922%

문제

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

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

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

입력

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

출력

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

 

풀이

숫자가 매우 크고(10의 6승) 주어진 시간이 매우 짧았다(0.15초). 먼저 DP를 어떻게 기록할 것인지 알아내야 했다.

Bottom → Top 방식에서 초항을 1부터 시작해 연산횟수를 기록해본다

1	2	3	4	5
0	1	1

1의 값을 가질 때는 연산이 필요없으므로 연산횟수는 0이 된다.

2의 값을 가질 때, 2는 1을 빼거나, 2로 나눌 수 있다. 그 중에서 최소값을 선택하고 1을 더한다. 두 값이 같으므로 결과값은 1이다.

3의 값을 가질 때, 3은 1을 빼거나, 3으로 나눌 수 있다. 그 중에서 최소값은 1항의 0값이고 1을 더해서 가져오면 3은 1이 된다

 

1	2	3	4	5
0	1	1	2	3

4의 값을 가질 때, 4에서 1을 빼거나 2를 나눌 수 있다. 그 중에서 최소값은 1로 같으므로 1+1=2를 가져온다

5의 값을 가질 때 2와 3으로 나눌 수 없으므로 4의 값을 가져온다 5의 값은 3으로 고정된다

 

1	2	3	4	5	6
0	1	1	2	3	2

6의 값을 가질 때, 6은 2로도 나눠지고 3으로도 나눠진다. 그리고 1도 뺄 수 있다. 6을 2로 나눈 3의 값은 1, 6을 3으로 나눈 2의 값은 1,

6에서 1을 뺀 5의 값은 3이다. 이 중 최소값은 1이므로 1+1=2가 된다. 즉 2와 3 둘 모두로 나눠질 때, 3개를 비교해야 한다.

 

조건문으로 가져오기

증가하는 i항에 대해서 i항을 먼저 분석한 다음 조건에 따라 나누어준다. i항이 2와 3으로 모두 나누어 떨어질 수 있는지, 2로만 나누어 떨어지는지, 3으로만 나누어 떨어지는지에 대해 경우를 나눌 수 있다.

2와 3 모두로 나눌 수 있는 경우: dp[N/2] , dp[N/3], dp[N-1] 중 최소값에 1을 더함

2로 나눌 수 있는 경우: dp[N/2], dp[N-1] 중 최소값에 1을 더함

3으로 나눌 수 있는 경우: dp[N/3], dp[N-1] 중 최소값에 1을 더함

2와 3으로 나눌 수 없는 경우: dp[N-1]에 1을 더함

import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Integer[] dp = new Integer[N+1];
		dp[1]=0;
		for(int i=2;i<N+1;i++) {
				if(i%2==0&&i%3==0) {
					dp[i]=Math.min(Math.min(dp[i/2], dp[i/3]),dp[i-1])+1;
				}else if(i%2==0) {
					dp[i]=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 {
					dp[i]=dp[i-1]+1;}}
		System.out.print(dp[N]);}}

코드 개선

꼭 나눠지는 것을 확인하고 계산할 필요가 없었다. 먼저 나누고 나누어 떨어지지 않는 수인 경우 나머지를 더해 -1연산을 더해줄 수 있다.

예를 들어 나누어 2와 3모두로 나누어 떨어지지 않는 7을 살펴보면

1	2	3	4	5	6	7
0	1	1	2	3	2	3

7은 2와 3 모두로 나누어 떨어지지 않지만 일단 2나 3으로 나눈다.

7을 먼저 2나 3으로 나누면, 3 또는 2가 되고 각각의 나머지는 모두 1이다. 즉 -1 연산은 각각 1번을 시행한다.(7%2, 7%3)

dp[7] = dp[7/3]+7%3 과 dp[7/2]+7%2 중 최소값을 선택한다

 

일반화하면

dp[i] = dp[i/2] + i%2 와 dp[i/3] + i%3 중 최소값을 선택한 후 1을 더한다

import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Integer[] dp = new Integer[N+1];
		dp[0]=0; dp[1]=0;
		for(int i=2;i<N+1;i++) {
			dp[i]=Math.min(dp[i/2]+i%2,dp[i/3]+i%3)+1;
		}
		System.out.print(dp[N]);
}}