글 읽기 - 제 풀이의 논리가 틀린 이유를 알고 싶습니다.

ktj7916 3년 전 0

클립보드의 개수또한 염려를 해야한다고생각을했고 (ex 복붙붙붙)

그렇기에 찾으려하는 숫자의 /2까지 for문을 돌면서 약수인 것들을 dp로 판단하려했습니다.

홀수일 경우 그 뒷숫자에서 -1하는 경우를 상정했구요.

왜 순수한 dp로는 안되는건가요??

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static int[] dp = new int[10001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());
        System.out.println(getNum(S));
    }

    public static int getNum(int num) {
        if (num > 1) {
            if (dp[num] != 0)
                return dp[num];
            else if (num % 2 == 0) {
                int temp = num;
                for (int i = 2; i <= num / 2; i++) {
                    if (num % i == 0)
                        temp = Math.min(temp, getNum(i) + num / i);
                }
                return dp[num] = temp;
            } else {
                return dp[num] = Math.min(getNum(num + 1) + 1, num);
            }
        } else
            return 0;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 풀이의 논리가 틀린 이유를 알고 싶습니다.

ktj7916 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말