문제
정수 N이 주어졌을 때, 다음 세 가지 연산을 사용하여 N을 1로 만드는 데 필요한 최소 연산 횟수를 구하는 문제다.
- 연산 1: X가 3으로 나누어 떨어지면 3으로 나눈다.
- 연산 2: X가 2로 나누어 떨어지면 2로 나눈다.
- 연산 3: X에서 1을 뺀다.
입력
- 첫째 줄: 정수 N (1 이상 1,000,000 이하)
출력
최소 연산 횟수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 | 1 |
10 | 3 |
풀이
재귀를 통해 N을 3으로 나누는 경로와 2로 나누는 경로를 모두 탐색하고, 나머지 처리를 위한 추가 연산 횟수를 더해 최솟값을 반환한다.
recur(N, count)재귀 함수를 정의한다.- N이 1 미만이면
count를 반환한다. - 3으로 나눈 결과:
recur(N/3, count + 1 + N%3)(나머지만큼 1 빼기 선행) - 2로 나눈 결과:
recur(N/2, count + 1 + N%2)(나머지만큼 1 빼기 선행) - 두 결과 중
Math.min으로 최솟값을 반환한다.
핵심 아이디어: N % 3만큼의 -1 연산과 ÷3을 한 번에 묶어 재귀 깊이를 줄인다. 단, 이 구현은 메모이제이션 없는 순수 재귀이므로 N이 클 경우 중복 계산이 발생한다. 실제 DP 풀이에서는 dp[i] = min(dp[i-1]+1, dp[i/2]+1, dp[i/3]+1) 점화식을 사용한다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day27BOJ1463일로만들기 { // 1463 1로 만들기
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
System.out.println(recur(N, 0));
sc.close();
}
static int recur(int N, int count) {
if (N < 2)
return count;
return Math.min(recur(N / 2, count + 1 + (N % 2)), recur(N / 3, count + 1 + (N % 3)));
}
}복잡도
- 시간: O(log^2 N) — 재귀 분기마다 N이 2 또는 3으로 줄어들며, 두 경로를 모두 탐색
- 공간: O(log N) — 재귀 호출 스택 깊이