BOJ1463_1로 만들기

개요

최단거리로 1에 도달할 수 있는 경우를 구현해봅시다

문제 접근

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

정수$N$의 범위 : 0 < $N$ < 10000001

제한시간은 0.15초로 해당 문제도 반복문으로 접근을 해보았다.

여기서 제한 조건을 보면

3으로 나누어 "떨어지면" 3으로 나눈다

잘못 생각하면 3으로 나누어 떨어지면 무조건 3으로 나누어야 될거라 생각했지만

이것은 위 문제의 힌트다 10 -> 9인걸 보았을 때
3 혹은 2로 나누어진다고 무조건적으로 나누어 생각하는게 아니라 결국 최단거리를 구하는 것이다.

만약 $N$이 5인 경우를 살펴보면 위 그림과 같이 표현할 수 있을거 같다
(3과2는 다음 수가 무조건 1이기 때문에 생략)

$N$이 9인 경우는 다음과 같다
(불가능한 경우는 그림에서 제외했다)

$N$이 10인경우 사진과 같이 $N=5$ 일때와 $N=9$일때를 포함하고 있다
그렇기에 해당문제도 부분 구조를 가지고 있는 것을 확인할 수있고
bottom-up 방식으로 코드를 구현할 수 있을거 같다

코드를 구현하기 앞서
위 그림들을 점화식으로 나타낸다면

$dp[10]=Math.min(dp[5],dp[9])+1$
단계가 한차례 늘어났기 때문에 $+1$을 해준다.

하지만 모든식이 이런건 아니다
만약 $N=12$이면 위 세가지 연산을 모두 적용 해볼 수 있을 것이다 $N=12$인 식은 아래와 같다

$dp[12]=Math.min(Math.min(dp[6],dp[4]),dp[11])+1$
결국 $N$이 만족하는 모든 연산 몫에 대해서 대소 비교를 해줘야한다

필자는 이런 가변적인 식에서 다음과 같이 생각을 해보았다.

int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
int c = Integer.MAX_VALUE;

애초에 케이스 3개를 전부 비교한다면??
$a$ <= 3으로 나누었을 때 0이면
$b$ <= 2로 나누었을 때 0이면
$c$ <= -1

그렇다 각 케이스마다 가능한 경우를 각자 $a,b,c$에 저장하여
세 개를 전부 비교하면 된다

이를 구현한 코드이다

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Q1463 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		
		int[] dp = new int[n + 1];
		// 정수가 1인경우는 0
        dp[1] = 0;
		
		for(int i = 2; i <= n; i++) {
			int a = Integer.MAX_VALUE;
			int b = Integer.MAX_VALUE;
			
			if(i % 2 == 0)
				a = dp[i/2] + 1;
			
			if(i % 3 == 0)
				b = dp[i/3] + 1;
			
			int c = dp[i-1] + 1;
			
			dp[i] = Math.min(Math.min(a,b),c);
		}
		
		bw.write(String.format("%d", dp[n]));
		bw.close();
	}

}

$dp$배열길이를 10,000,001으로 초기화하기에 메모리가 초과되어 다음과 같이 배열을 초기화 하였다