[백준/JAVA] 1463번: 1로 만들기

🔺 문제

1463번: 1로 만들기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int D[];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        D = new int[N + 1];
        D[1] = 0;
        
        for(int i = 2 ; i <= N ; i++) {
            D[i] = D[i - 1] + 1;                                // 🔔 -1 먼저 하기
            if(i % 2 == 0) D[i] = Math.min(D[i], D[i/2] + 1);   // % 2 연산
            if(i % 3 == 0) D[i] = Math.min(D[i], D[i/3] + 1);   // % 3 연산
        }
        
        System.out.println(D[N]);
    }
}

✅ 해결 아이디어
✔ DP - 점화식 (Bottom-Up 방식)
→ D[i] : i에서 1로 만드는 데 걸리는 최소 연산 횟수

 

💥 유의사항

⇨ DP문제에서는 초기값 설정하는 거 잊지 말기!

⇨ DP 문제 해결 과정

       1) 테이블 정의하기

       2) 점화식 찾기

       3) 초기값 설정하기

---

🔺 다른 풀이들

- 멋진 풀이.. 감사합니다.. (복습용)

[알고리즘-JAVA] 백준 알고리즘 1463번 - 1로 만들기

 

       

- 점화식 찾는 과정까지... 👍👍 (복습용)

[백준] 1463번 1로 만들기 - Java, 자바

[백준/1463/Java] 1로 만들기 - DP 풀이

 

 

- 6으로 나눠지는 경우까지 생각해서 푸심

[백준] 1463번 : 1로 만들기 – JAVA [자바]

---

💬 느낀 점

점화식 이제부터 시작이야~~

 

 

1회독	2회독	3회독	4회독	5회독
V	230705	240309

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편