boj 1463 1로 만들기

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

1463번: 1로 만들기

 

시험삼아 포스팅하는 문제로, 간단한 dp 문제입니다.

 

정수 X에 적용되는 연산들을 적절히 사용해서 X를 1로 만드는데 연산을 사용하는 횟수의 최솟값을 출력하는 문제입니다.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다. → X가 3으로 나누어 떨어지면 X/3보다 횟수 +1

2. X가 2로 나누어 떨어지면, 2로 나눈다. → X가 2로 나누어 떨어지면 X/2보다 횟수 +1

3. 1을 뺀다. → X-1보다 횟수 +1

 

1, 2, 3번의 최솟값을 찾으면 되겠습니다.

(X=1일 때 횟수가 0이므로 2부터 반복문을 돌려줍니다.)

 

(Java 소스 추가하였습니다.)

 

 

[C++]

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1000001], N;
 
int ans() {
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;
 
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1);
        }
    }
    
    return dp[N];
}
 
int main() {
    cin >> N;
    cout << ans() << '\n';
 
    return 0;
}

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int dp[];
    static int N;
 
    static void func() {
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;
 
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        
        System.out.println(dp[N]);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        dp = new int[N + 1];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}