백준 1463번 1로 만들기 자바 Java (☆공부 259일차)

1463 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

 

 

---

백준 1463번 문제 1로 만들기

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초 (하단 참고)	128 MB	252235	84145	53744	32.502%

문제

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

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

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

입력

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

출력

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

제한

 

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/206

공부 120일차: 백준1463번 1로 만들기 자바 java

4달 전에 푼 문제

 

 

2부터 10까지 구해보면서, 어떤 공통점이 있는지 도출해내야 한다

그전수의 최소값에 1을 더하거나(-1한 것) 3이나 2로 나눈 몫에 1을 더하거나(나눈 연산) 하면 된다는 규칙이 보인다

 

1. dp[] 점화식

2. 재귀 메서드

 

이전에 1번으로 풀어봤으니 2번으로 해보기로 했다

실제로 재귀 메서드를 이용하는 게 메모리와 시간 두 측면에서 더 낫다

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
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());
        
        System.out.println(recursion(n, 0));
    }
 
    // 재귀
    static int recursion(int n, int count) {
        if(n < 2) {
            return count;
        }
        // n%2 혹은 n%3 -> -1하는 횟수와 같다
        return Math.min(recursion(n/2, count+1+n%2), recursion(n/3, count+1+n%3));
    }
}

 

 

 

---