백준_1로만들기_동적계획법(java)

1로 만들기

1. 문제

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

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

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

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

solution ) 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        int[] res = new int[n+1];
        res[0] = res[1] = 0;
 
        for(int i = 2; i <= n; i++){
            res[i] = res[i-1]+1; 
            if(i % 3 == 0) res[i] = Math.min(res[i], res[i/3]+1); 
            else if(i % 2 == 0) res[i] =  Math.min(res[i], res[i/2]+1);
        }
        System.out.println(res[n]);
        sc.close();
    }
 
}

TestCase )

2 입력 -> 1

10 입력 -> 3

Problem )

1. 처음에 일단 백준에서 제출해야하는 코드의 형식을 몰라 헤맸다.

2. 문제를 단순하게 생각해 최솟값을 찾는 것이 아니라 그저 횟수를 찾았다.

10 -> 9 -> 3 -> 1 (3회 : 정답)

10 -> 5 -> 4 -> 2 -> 1 (4회 : 나의 오답)

3. 그래서 다른 사람의 답안을 봤을때도 바로 이해가 되지 않았다가 

    문의사항에서 나와 같은 질문을 한 사람에게 달린 답변을 보고 깨달았다. 

    최소값을 묻는 문제라는 것을 !!!!!!!!!!!!!! 아직 좀 어렵지만 좀 더 해 볼 만해 보인다. 

* 백준 풀이 방법

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        System.out.println();
        sc.close();
    }
}