신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

 

문제

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

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

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

 

입력

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

 

출력

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

 

제 입력

2

 

예제 출력

1

 

예제 입력

10

 

예제 출력

3

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex1463 {
    
    // d[n] = d[n-1] +1;
    // d[n] = d[n/3] +1;
    // d[n] = d[n/2] +1;
    private static int[] d;
    private static int dp(int k) {
        if(k <= 1) {
            d[k] = 0;
            return 0;
        }else if(k <= 3 && k > 1) {
            d[k] = 1;
            return d[k];
        }
        // memoization
        if(d[k] > 0) {
            return d[k];
        }
        
        d[k] = dp(k-1) +1;
        if(k % 2 ==0) {
            int temp =  dp(k/2) + 1;
            if(d[k] > temp) {
                d[k] = temp;
            }
        }
        
        if(k % 3 == 0) {
            int temp = dp(k/3) + 1;
            if(d[k] > temp) {
                d[k] = temp;
            }
        }
        return d[k];
    }
    
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int n = Integer.parseInt(br.readLine());
            d = new int[n+1];
            System.out.print(dp(n));
        } catch (Exception e) {
            // TODO: handle exception
            e.printStackTrace();
        }
    }
}​

 

 

 

 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기