1 minute read

πŸ“Œ λ‚œμ΄λ„

πŸ₯ˆ Silver 3


πŸ“Œ 문제

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


image


πŸ“Œ 풀이

와! μ§„μ§œ λ„ˆλ¬΄λ‚˜λ„ μ–΄λ €μš΄ λ¬Έμ œμ˜€λ‹€.
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으둜 λ³€κ²½ν•˜λ©΄ λœλ‹€.



개인 곡뢀 기둝용 λΈ”λ‘œκ·Έμž…λ‹ˆλ‹€.
ν‹€λ¦¬κ±°λ‚˜ 였λ₯˜κ°€ μžˆμ„ 경우 μ œλ³΄ν•΄μ£Όμ‹œλ©΄ κ°μ‚¬ν•˜κ² μŠ΅λ‹ˆλ‹€.😁