BOJ 1463

2020-03-30

위 문제는 백준 사이트의 알고리즘 1463 문제에 관한 설명입니다.

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

### 초기에 작성했던 코드

 import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int count = 0;
		while(N != 1)
		{
			if(N % 3 ==0)
				N/=3;
			else if(N % 2 ==0)
				N/=2;
			else
				N-=1;
			count++;
			System.out.println(N);
		}
		System.out.println(count);
	}

}

처음에는 바로 위 코드 처럼 “3으로 나누거나 2로 나누거나 아니라면 -1시킨다” 라고 생각을 했습니다.

그러나 이렇게 하면 10을 입력했을 때

10 -> 5 -> 4 -> 2-> 1로 4가 출력이 됩니다.

그러나 정답은

10 -> 9 -> 3-> 1로 3이 출력 되어야 합니다.

### 최종 코드


import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner =new Scanner(System.in);
		int N = scanner.nextInt();
		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]);
	}
}

Bottom-up 방식이라고 하는데 다음번엔 Top-down 방식으로도 풀어봐야겠습니다.

2와 3을 예시로 들어봅시다.

dp2 = dp1 + 1;

그렇다면

 if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2]+1);

에서 dp2과 dp2/2+1(1)이기에 min값인 1이 dp[2]에 저장됩니다.

dp[3]도 같은 과정 입니다.

dp3 = dp2+1

	if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3]+1);

dp[3]은 dp3와 dp3/3+1의 값으로 결정이 되는데

이때 dp[3/3] +1은 1과 같으므로 2보다 값이 작아서 dp[3]에는 1이 저장됩니다.

1로 만들기