공부 120일차: 백준1463번 1로 만들기 자바 java

1463 1로 만들기

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

1463번: 1로 만들기

 

 

 

 

---

백준 1463번 문제 1로 만들기

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://hongjw1938.tistory.com/47#1.-%EA%B0%9C%EC%9A%94

우선 다이나믹 프로그래밍, 즉 동적계획법에 대해 알고 싶어서 위의 블로그 글을 한 번 읽었다

 

 

2부터 10까지 구해보면서, 어떤 공통점이 있는지 도출해내야 한다

그전수의 최소값에 1을 더하거나(-1한 것) 3이나 2로 나눈 몫에 1을 더하거나(나눈 연산) 하면 된다는 규칙이 보인다

 

 

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    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[1_000_001];
        
        dp[1] = 0;
        for(int i = 2; i < n+1; i++) {
            dp[i] = dp[i-1]    + 1;    // 1은 -1하는 연산 더한 것
            if(i % 3 == 0) {    //3으로 나누어 떨어진다면(여기서 6의 배수도 같이 계산)
                dp[i] = Math.min(dp[i], dp[i/3]+1);    // 1은 /3하는 연산 더한 것
            }
            if(i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i/2]+1);    // 1은 /2하는 연산 더한 것
            }
        }
        System.out.println(dp[n]);
                
    }
 
}
 

 

주석에 설명을 적었다

 

 

---