백준 1436번 : 1로 만들기 자바

🧫 문제 분석

✔️ 출처

1로 만들기 실버 3

 

📖 문제

 

3으로 나눴을 때 

2로 나눴을 때 

1을 뺐을 때  

 

3가지 경우 중 더 작은 값을 찾으면 된다.

 

 

6을 예시로 보면

6 / 3 의 최솟값 dp[6 / 3] + 1,

6 / 2 의 최솟값 dp[6 / 2] + 1,

6 - 1 의 최솟값 dp[6 - 1] + 1

dp[2] = 1, dp[3] = 1, dp[5] = 3

+1을 해주는 이유는 6에 대해 연산을 해주었기때문이다. 

 

따라서 dp[6] = 2이다.

 

 

 

---

🔅 문제 풀이

import java.io.*;

public class Main {

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

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

        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + 1;

            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1,dp[i]);
            }

            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
            }
        }

        bw.write(dp[n]+"\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1. if - else 를 잘 구분해서 쓸 줄 알아야한다. 이 문제도 else를 붙여서 계속 틀렸던 것이다. else 를 써야할 때를 잘 생각해보고 사용하자.