λ¬Έμ
λ¬Έμ λ§ν¬ https://www.acmicpc.net/problem/1463
- μ μ Xμ μ¬μ©ν μ μλ μ°μ°μ λ€μκ³Ό κ°μ΄ μΈ κ°μ§ μ΄λ€.
- Xκ° 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ©΄, 3μΌλ‘ λλλ€.
- Xκ° 2λ‘ λλμ΄ λ¨μ΄μ§λ©΄, 2λ‘ λλλ€.
- 1μ λΊλ€.
- μ μ Nμ΄ μ£Όμ΄μ‘μ λ, μμ κ°μ μ°μ° μΈ κ°λ₯Ό μ μ ν μ¬μ©ν΄μ 1μ λ§λ€λ €κ³ νλ€. μ°μ°μ μ¬μ©νλ νμμ μ΅μκ°μ μΆλ ₯νμμ€.
- 첫째 μ€μ 1λ³΄λ€ ν¬κ±°λ κ°κ³ , 106λ³΄λ€ μκ±°λ κ°μ μ μ Nμ΄ μ£Όμ΄μ§λ€.
- 첫째 μ€μ μ°μ°μ νλ νμμ μ΅μκ°μ μΆλ ₯νλ€.
μμ΄λμ΄
- μ°μ° νμλ₯Ό μ μ₯ν λ°°μ΄μ λ§λ€μ΄μ 1, 2, 3μ μ΄κΈ°κ°μΌλ‘ μ μ₯νλ€.
- 1μ μ°μ°νμκ° 0, 2λ μ°μ°νμκ° 1, 3μ μ°μ°νμκ° 1λ‘ μ μ₯νλ€.
- 4λΆν° NκΉμ§ λ°λ³΅λ¬Έμ λ리면μ κ°μ μ μ₯νλλ°, forλ¬Έ μμν λ iλ²μ§Έ λ°°μ΄κ°μ i-1λ²μ§Έ λ°°μ΄κ° + 1λ‘ μ μ₯νλ€. (iμμ 1μ λΉΌλ©΄ i-1μ΄ λλ―λ‘)
- κ·Έλ¦¬κ³ λ§μ½ iκ° 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ©΄ iλ₯Ό 3μΌλ‘ λλ λ°°μ΄κ°μμ 1 λν κ°κ³Ό νμ¬κ° κ·Έλ¦¬κ³ i-1λ²μ§Έ λ°°μ΄ κ°μμ 1 λν κ°μ€ μ μΌ μμ κ°μ iλ²μ§Έ λ°°μ΄μ μ μ₯νλ€.
- κ·Έ λ€ iκ° 2λ‘ λλμ΄ λ¨μ΄μ§λ€λ©΄ iλ₯Ό 2λ‘ λλ λ°°μ΄κ°μμ 1 λν κ°κ³Ό νμ¬κ° κ·Έλ¦¬κ³ i-1λ²μ§Έ λ°°μ΄ κ°μμ 1 λν κ° μ€ μ μΌ μμ κ°μ iλ²μ§Έ λ°°μ΄μ μ μ₯νλ€.
κ²ͺμ μνμ°©μ€
- X
μ½λ
import java.util.*;
import java.io.*;
public class BOJ1463 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// μ°μ° νμ μ μ₯
int arr[] = new int[N + 1];
// 1, 2, 3μΌλ μ΄κΈ°κ°λ€ μ μ₯
arr[1] = 0;
if(N > 1){
arr[2] = 1;
}
if(N > 2){
arr[3] = 1;
}
for(int i = 4; i <= N; i++){
// iλ²μ§Έ κ°μ μ λ°°μ΄ κ°μ 1μ λν κ°μΌλ‘ μ μ₯
arr[i] = arr[i - 1] + 1;
// 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ€λ©΄
if(i % 3 == 0){
// 3μΌλ‘ λλ κ°μμ 1μ λν κ°κ³Ό
// ν΄λΉ κ°λ³΄λ€ 1μμ κ°μμ 1 λν κ° μ€
// λ μμ κ°μ ν΄λΉ λ°°μ΄ κ°κ³Ό λΉκ΅ν΄ λ μμ κ°μ μ μ₯
arr[i] = Math.min(Math.min(arr[i / 3] + 1, arr[i - 1] + 1), arr[i]);
}
// 2λ‘ λλμ΄ λ¨μ΄μ§λ€λ©΄
if(i % 2 == 0){
// 2μΌλ‘ λλ κ°μμ 1μ λν κ°κ³Ό
// ν΄λΉ κ°λ³΄λ€ 1μμ κ°μμ 1 λν κ° μ€
// λ μμ κ°μ ν΄λΉ λ°°μ΄ κ°κ³Ό λΉκ΅ν΄ λ μμ κ°μ μ μ₯
arr[i] = Math.min(Math.min(arr[i / 2] + 1, arr[i - 1] + 1), arr[i]);
}
}
System.out.println(arr[N]);
}
}
'μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Java] BOJ 2606 λ°μ΄λ¬μ€ (0) | 2024.07.27 |
---|---|
[Java] BOJ 2579 κ³λ¨ μ€λ₯΄κΈ° (0) | 2024.07.27 |
[Java] BOJ 1003 νΌλ³΄λμΉ ν¨μ (0) | 2024.07.26 |
[Java] BOJ 17219 λΉλ°λ²νΈ μ°ΎκΈ° (6) | 2024.07.24 |
[Java] BOJ 11399 ATM (2) | 2024.07.23 |