글 읽기 - DP 질문

diekfk1 1년 전 0

그리디 방법으로 문제를 푼 뒤, DP가 약해서 DP 방식으로 풀어봤는데 틀렸다고 나옵니다.

반례 좀 찾아주세요

import java.io.IOException;

public class Main {

    public static void main(String[] args) {
        int n = readInt();
        int[] dp = new int[n + 1];

        if (n >= 2) dp[2] = 1;
        if (n >= 5) {
            dp[4] = 2;
            dp[5] = 1;
        }

        for (int i = 6; i <= n; i++) {
            if (i % 5 == 0) dp[i] = dp[i - 5] + 1;
            else if (i % 2 == 0) dp[i] = dp[i - 2] + 1;
            else dp[i] = Math.min(dp[i - 5], dp[i - 2]) + 1;
        }

        System.out.println(dp[n] == 0 ? -1 : dp[n]);
    }

    private static int readInt() {
        int c, n = 0;

        try {
            n = System.in.read() & 15;
            while ((c = System.in.read()) > 32)
                n = (n << 3) + (n << 1) + (c & 15);
        } catch (IOException ignored) {}

        return n;
    }
}

pill27211 1년 전 1

반례입니다.

Input)

Output)

-1

Answer)

diekfk1 1년 전 1

아.. 생각을 짧게 했네요

if문을 하나 더 만들어줘야 했는데.. 감사합니다!

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

문제

문제

출처

ICPC

DP 질문

diekfk1 1년 전 0

pill27211 1년 전 1

diekfk1 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말