글 읽기 - 반례 질문드립니다

bruce1010 1년 전 0

반례가 도저히 생각나지 않아서 질문드립니다.

점화식은 i번째 잔을 마셨을때를 기준으로 i-1번째 잔을 마시지 않은 경우를 b[i][0], i-1번째 잔을 마신 경우를 b[i][1]으로 두면 b[i][0] = max(b[i-1][0], b[i-1][1]) + a[i], b[i][1] = b[i-1][0] + a[i]가 됨을 활용해 b에 저장된 최댓값을 반환하였습니다. 어떤 반례가 있을까요?

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
a.append(50000)
b = [[a[0], 0], [a[1], a[0] + a[1]]]
if n > 2:
  t = a[0]
  for i in range(2, n):
    b.append([t + a[i], b[i - 1][0] + a[i]])
    if t < max(b[i - 1]):
      t = max(b[i - 1])
  print(max(b[n - 1] + [t]))
else:
  print(a[0])

314programs 1년 전 0

답: 117

출력: 63

입력:

2
63
54

마지막 조건만 고치면 맞아요

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

문제

문제

출처

ICPC

반례 질문드립니다

bruce1010 1년 전 0

314programs 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말