[백준 1463번] 1로 만들기 - (Java/python)

문제 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

Idea

X 로 할수있는 연산은 3가지가 있다.

1. x/3

2. x/2

3. x-1

각각의 연산을 하게 되면 x의 크기는 작아진다. 3가지 연산중 한가지를 사용해 1로 만들어야 되고 그 연산 횟수가 최소가 되어야 한다.

예를 들어 x가 12라고 하면 12/3 = 4 가 될수가 있고 12/2 = 6 이 될수가 있고, 12-1 = 11 이 될수가 있다. 

즉 12를 1로 만드는 최소 횟수는 min(4를 1로 만드는 최소 횟수, 6을 1로 만드는 최소 횟수, 11을 1로 만드는 최소 횟수) + 1 로 표현 할 수 있다. 

이때 d 배열을 만들고 배열에는 해당 수를 1로 만드는 횟수를 저장한다고 할때 식을 다음처럼 세워줄 수 있다.

d[x] = min(d[x/3],d[x/2],d[x-1])+1

 

한가지 주의할 점은 항상 3가지 연산이 다 가능한것이 아니라 x가 3으로 나누어 떨어질때, 2로 나누어 떨어질때 각 연산을 적용할수 있으므로 해당 조건을 추가해 주면 된다.

 

 

풀이

Java

import java.util.Scanner;

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

        int[] d = new int[n + 1];
        d[1] = 0;

        for (int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + 1;

            if (i % 2 == 0) {
                d[i] = Math.min(d[i / 2] + 1, d[i]);
            }

            if (i % 3 == 0) {
                d[i] = Math.min(d[i / 3] + 1, d[i]);
            }

        }

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

 

 

Python

n = int(input())

d = [0]*(n+1)

d[1] = 0

for i in range(2,n+1):
    d[i] = d[i-1] + 1
    if i%2==0:
        d[i] = min(d[i],d[i//2]+1)
    if i%3==0:
        d[i] = min(d[i],d[i//3]+1)


print(d[n])