글 읽기 - 4퍼에서 못넘어가는데 반례가 있을까요?

nbo5548 1년 전 0

직접 예제를 만들어서도 해보고 게시판에 있는 반례들도 해보았는데 문제없이 잘 돌아갔습니다.

어떠한 반례가 있는지 궁금합니다..

n = int(input())

data = []
for i in range(n-1):
    a, b = map(int, input().split())
    data.append([a,b])

k = int(input())
#print(data)
#print(f"n : {n}, k : {k}")
ans = [0] * n
check = [0] * n
_ans = 1e9
if n == 1: 
    ans[n-1] = 0
    _ans = 0
elif n == 2:
    ans[n-1] = data[0][0] # 작은점프
    _ans = ans[n-1]
elif n == 3:
    ans[n-1] = min(data[0][0]+data[1][0], data[0][1])
    _ans = ans[n-1]
else:
    ans[0] = 0
    ans[1] = data[0][0]
    ans[2] = min(data[0][0]+data[1][0], data[0][1])
    for i in range(3, n):
        ans[i] = min(ans[i-2]+data[i-2][1], ans[i-1]+data[i-1][0]) # 우선 작점, 큰점만 고려
    _ans = ans[-1]
    for i in range(n): check[i] = ans[i]
    
    # 각 돌에서 매큰점했을때 고려하여 최솟값구함
    for i in range(3, n):
        check[i] = check[i-3] + k
        if i<n-1: 
            check[i+1] = check[i] + data[i][0]
            for j in range(i+2, n):
                check[j] = min(check[j-2]+data[j-2][0]+data[j-1][0], check[j-2]+data[j-2][1])
        _ans = min(_ans, check[n-1])
        #print(check)
        for i in range(n): check[i] = ans[i]
            
print(_ans)

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

문제

문제

출처

ICPC

4퍼에서 못넘어가는데 반례가 있을까요?

nbo5548 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말