[055] 1463. 1로 만들기

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

1463번: 1로 만들기

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 세가지의 연산을 활용하면서 사용 횟수의 최소를 구하기

 

 

 

🧶 풀이과정 

 

dp 기본 문제인데 역시 내가 dp는 약해서 끙끙대는 과정이 좀 있었다.

연산은 다음과 같이 처리할 수 있다

 

1. dp 배열을 만든다

2. dp 배열을 순회하면서 n까지의 계산값을 저장한다

3. n의 계산값을 출력한다

 

이것을 기본으로 두고, 이 연산을 수행하기 위한 방법을 채택하자.

여기에서 계산값은 셋 중 하나이다

1. 3으로 나누기 

2. 2로 나누기

3. 1을 빼기

 

세가지 중 하나를 선택하는 건, 1과 2가 불가능할 경우 사용할 수 있는 1을 채택한다.

그리고 if문을 통하여 2나 3으로 나누었을 경우에 나오는 값이 -1의 값보다 작다면, 여기에선 최소횟수이기 때문에 작은 값을 넣는다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

public class Q1463 {

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

        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n + 1];

        dp[0] = dp[1] = 0;
        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]);

        br.close();

    }

}