백준 - 1463 - 1로 만들기

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

1463번: 1로 만들기

 

 

 

문제를 딱 보고나서 점화식이라는 방법이 떠오르지 않아 그냥 구현했더니 틀렸다.

찾아보니까 점화식을 사용해서 푸는 문제라고 나와있었다.

 

잊어버릴 수 있으니 정리를 해보려고 한다.

 

 - 1을 뺄 때는 d[i] = d[i-1] + 1
- 2로 나눌 수 있을 때는 d[i] = d[i/2] + 1
- 3으로 나눌 수 있을 때는 d[i] = d[i/3] + 1

초기값은 dp[1] = 0 으로 설정한다.

 

* 점화식

i 를 계산하는 방법에는 총 3가지가 있다.

• 2로 나눈 나머지가 0일 경우, 2로 나눈다.
• 3으로 나눈 나머지가 0일 경우, 3으로 나눈다.
• 1을 뺀다.

i 의 최소 연산 횟수를 저장하는 배열을 dp 라고 정의할 때, dp[i] 의 값은 다음과 같다.

dp[i] = Math.min(dp[i-1] + 1, dp[i/2] + 1, dp[i/3] + 1);

 

<코드>

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

public class B_1463 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int X = Integer.parseInt(br.readLine());
        int[] dp = new int[X+1];

        dp[1] = 0;

        for(int i = 2; i <= X; 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[X]);
    }
}

 

 

 

 

참고 블로그 :
https://iseunghan.tistory.com/336
https://smartpro.tistory.com/24