[백준] 1463번 : 1로 만들기

문제

 

 

접근 방식

처음 풀어보는 DP문제로 백트래킹으로도 풀 수 있지만 시간제한이 빡빡한 문제이기 때문에

DP로 효율적으로 풀어야 풀 수 있는 문제다.

2를 1로 만드는 경우
2 - 1 >> 1
2 / 2 >> 1

3을 1로 만드는 경우
3 / 3 >> 1
3 - 1 - 1 >> 2

4를 1로 만드는 경우
4 / 2 / 2 >> 2
4 / 2 - 1 >> 2
4 - 1 - 1 / 2 >> 3
4 - 1 - 1 - 1 >> 3

 

가장 작은 경우를 예로 들어 2 ~ 4가 1이 되는 경우를 살펴보면 위와 같은데

4 / 2 / 2 순서로 계산하여 1이 되는 경우에는 숫자의 변화는 4 > 2 > 1이 될 것이고

해당 숫자의 인덱스에 계산 횟수를 기록한다 치면 {0, 2, 1, 0, 0} 이 된다.

 

여기서 알 수 있는 점은 연산을 할 때마다 연산 결과의 인덱스가 이전 횟수 + 1이라는 것이다.

count[n] = 0

count[n - 1] = count[n] + 1
count[n / 2] = count[n] + 1
count[n / 3] = count[n] + 1

 

즉, 위와 같이 인덱스가 점점 줄어들면서 1에 다다르게 됫을 때 최종 값이

가장 적은 연산 횟수인 것을 알 수 있다.

 

이를 그대로 코드로 구현하면 되는데 우선 DP 테이블에 연산 결과에 해당하는 인덱스까지

몇 번의 연산을 사용했는지를 기록하게 하고, 1부터 n까지 반복문을 돌면서

k - 1, k / 2, k / 3 번째 인덱스들에 이전까지의 연산 횟수 + 1에 해당하는 값들을 저장해준다.

 

주의해야 할 점은 2와 3으로 나누는 경우는 완전히 나누어 떨어질 때만 가능하며

나누는 경우가 1을 빼는것보다 효율적인지를 판단하기 위해

둘 중 더 작은 값을 기준으로 저장해줘야 한다.

풀이

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[] counts = new int[n + 1];

		for (int i = 2; i <= n; i++) {
			counts[i] = counts[i - 1] + 1;
			if (i % 2 == 0) counts[i] = Math.min(counts[i], counts[i/2] + 1);
			if (i % 3 == 0) counts[i] = Math.min(counts[i], counts[i/3] + 1);
		}

		System.out.println(counts[n]);
	}
}