글 읽기 - 나무 베기 DP로 풀고 있는데 계속 실패가 되네요

viadark 4년 전 0

DP로 풀고있는데 계속 오답이 나옵니다..

혹시 반례 있는지 궁금 합니다.

import sys
import math
inp = sys.stdin.readline().rstrip().split(" ")
n = int(inp[0])
target = int(inp[1])
inp2 = sys.stdin.readline().rstrip().split(" ")
num = list(map(int, inp2))
num.sort(reverse=True)
dp = [0] * n
if n == 1:
    print(num[0] - target)
else:
    dp[1] = num[0] - num[1]
    res = -1
    for i in range(2, n):
        dp[i] = dp[i-1] + i * (num[i-1] - num[i])
        if dp[i] == target:
            res = num[i]
            break
        elif dp[i] > target:
            #print("here???")
            diff = dp[i] - target
            res = num[i] + (diff // i)
            break
    
    if res == -1:
        if dp[n-1] > target:
            #print("here")
            diff = dp[n-1] - target
            res = num[n-1] + (diff // (n-1))
        else:
            diff = target - dp[n-1]
            res = num[n-1] - math.ceil(diff / n)
    #print(dp)
    print(res)

viadark 4년 전 0

dp[1] 에서 바로 target을 넘었을 경우를 고려 안 하여 틀렸습니다...

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

문제

문제

출처

ICPC

나무 베기 DP로 풀고 있는데 계속 실패가 되네요

viadark 4년 전 0

viadark 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말