[λ°±μ€] π₯ 1463 1λ‘ λ§λ€κΈ°
π λμ΄λ
π₯ Silver 3
π λ¬Έμ
https://www.acmicpc.net/problem/1463
π νμ΄
μ! μ§μ§ λ무λλ μ΄λ €μ΄ λ¬Έμ μλ€.
DP
κ° λͺ¨λ μκ³ λ¦¬μ¦ μ€μ μ΄λ‘ μ μ½μ§λ§, λ¬Έμ λ‘ μ²μ μ νμ λ, κ°μ₯ λν΄ν μκ³ λ¦¬μ¦μ΄λΌκ³ νλλ°, μ§μ§μΈ κ² κ°λ€.
μ²μμλ λ¨μνκ² /3μΌλ‘ λλκ³ , /2μΌλ‘ λλκ³ λλμ΄ λ¨μ΄μ§μ§ μμΌλ©΄, -1μ νλ λ°©μ
μΌλ‘ ꡬννμλ€.
νμ§λ§ 2λ²μ§Έ μμ λ₯Ό λ£μ΄λ³΄κ³ ν¬λν° μ€λ₯λ₯Ό μμλ€.
λ°λ‘ 10μμ κ°μ₯ λΉ λ₯΄κ² 1μ΄ λλ λ°©λ²μ 10->5->4->2->1
μ΄ μλλΌ 10->9->3->1
λ‘ 3λ²λ§μ λλ¬ν μ μλ€λ κ²μ΄μλ€.
μ μ΄κ²μ λ°κ²¬νκ³ λμ λ체 μ΄λ»κ² νμ΄μΌνλμ§ κ°λ μ‘°μ°¨ λμ§ μμλ€.
μ΄κ±Έ ν΄κ²°νλ €λ©΄ μ΄μ κ°μ λν λͺ¨λ μ΅μκ°μ΄ μμ΄μΌμ§λ§ κ·Έ κ²μ λΉκ΅ν¨μΌλ‘μ¨, λ€μ κ°μ μμλΌ μ μλκ² μλκ°? λΌλ μκ°μ΄ λ€μλ€.
κ·Έλ¬λ©΄ μ΄μ κ°μ λν μ 보λ₯Ό μ μ₯νκ³ μλ 곡κ°μ΄ νμνκ³ , κ·Έλ¬λ©΄ 10^6μ ν΄λΉνλ 곡κ°μ΄ νμνμ§ μλ
λΌλ μκ°μ΄ λ€μλ€.
λ무 λΉν¨μ¨μ μΈ κ² κ°μμ§λ§, μΌλ¨ ν΄λ³΄κΈ°λ‘ νμλ€.
κ·Έλμ 1μ 0
, 2μ 3μ 1
μ λ£κ³ , 4λΆν°λ /3, /2, -1 μ κ³μ°ν κ°μ μ£Όμμ μλ μ«μκ° κ°μ₯ μ μ κ²μ +1μ νμ¬ μ μ₯μ νμλ€.
κ·Έλ¬μ λ€μκ³Ό κ°μ΄ μ μ₯μ΄ λμλ€.
DPμ 맀μ΄λ§μ λ³Έ λ¬Έμ μλ€.
π Code
package DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class N1463 {
public static List<Integer> Mem;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int target = Integer.parseInt(st.nextToken());
Mem = new ArrayList<Integer>(Arrays.asList(0, 0, 1, 1));
int value;
for (int i = 4; i < target + 1; i++) {
Mem.add(TotalMakeToOne(i));
}
System.out.println(Mem.get(target));
System.out.println(1);
}
static int TotalMakeToOne(int num) {
return Math.min(Math.min(Mem.get(MakeToOne1(num)), Mem.get(MakeToOne2(num))), Mem.get(num - 1)) + 1;
}
static int MakeToOne1(int num) {
if (num % 2 == 0) {
return num / 2;
}
return num - 1;
}
static int MakeToOne2(int num) {
if (num % 3 == 0) {
return num / 3;
}
return num - 1;
}
}
package (μ΄λ¦); λ₯Ό λκ³ , class μ΄λ¦μ Main
μΌλ‘ λ³κ²½νλ©΄ λλ€.
κ°μΈ κ³΅λΆ κΈ°λ‘μ© λΈλ‘κ·Έμ
λλ€.
ν리거λ μ€λ₯κ° μμ κ²½μ° μ 보ν΄μ£Όμλ©΄ κ°μ¬νκ² μ΅λλ€.π