글 읽기 - 와인을 마시지 않는 경우가 왜 필요한가요?

kwr0113 3년 전 1

저는 문제를 보자마자 2579번 계단 오르기 문제랑 동일한 문제라고 생각했는데요

다른점은 마지막 계단은 꼭 밟아야 한다 와 마지막 와인을 마시지 않아도 된다 뿐이라고 생각해서

( n번째 와인 + n-1번째 와인 + n-3번째 와인까지 총합 ) 과 ( n번째 와인 + n-2번째 와인까지 총합 ) 두개를 비교해서 더 큰 값을 n번째 와인까지의 총합 에 넣었는데요

마지막에 출력할때 총 리스트의 최댓값을 찾으면 되지 않나요?

예제를 넣어보면 최종 값이 [6 16 23 28 33 32] 이렇게 저장이 됩니다

왜 n번째 총합을 구할 때 n번째 와인을 마시지 않는 경우를 고려해야 하는지 모르겠습니다

# 2156.PY

n = int(input())

grape = [int(input()) for _ in range(n)]
t_grape = [0 for _ in range(n)]

t_grape[0] = grape[0]

if n > 1:
    t_grape[1] = grape[0] + grape[1]
if n > 2:
    t_grape[2] = grape[2] + max(grape[0], grape[1])

for i in range(3, n):
    t_grape[i] = grape[i] + max(grape[i-1] + t_grape[i-3], t_grape[i-2])

print(max(t_grape))

a99azaz 3년 전 3

100

에서 해당 소스는 301을 출력하지만 실제 답은 400입니다.

pmn0001 3년 전 1

1000

을 보시면 왜 마시지 않는 것을 고려하는지 이해되실겁니다

중간에 마시지 않는다면 답은 4000인데

중간에 뭘 마셔버리면 답이 3001이 되지요

kwr0113 3년 전 0

왜 n번째 포도주를 마시지 않는 경우를 고려해야하는지는 이해하지 못했으나

제시해주신 반례를 이용해서 정답 맞추는데에는 성공하였습니다

감사합니다

pmn0001 3년 전 4

제가 이해하기로는 n번째 포도주를 마시지 않는 경우. 라기보다는

1 2 3 4 5 6

ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ

현재 5번째 잔에서 제일 많이 마실 수 있는 것을 고려한다고 해볼게요

작성자님의 코드에서는 5번째에서 t_g[3] + g[5] 와 t_g[2]+g[4]+g[5] 둘 중 하나를 고르게 되겠죠?

문제가 어디서 발생하냐면 t_g[2]+g[4]+g[5] 를 선택했을 때에요, t_g[2]+g[4]+g[5] 보다 t_g[2]+g[5]+g[6]이 더 큰데 이미 4를 마셔버려서 6을 고르고싶어도 고를수가 없어져버리죠?

그래서 두단계 건너뛰는 것까지 생각하는거라고 저는 이해했어요(n번째를 마시지 않는 경우라기보다, 저는 두단계 건너뛰는 것이라고 이해했네요 사람마다 이해하기 쉬운 방식이 있는 거니까요)

그래서 5번째를 고려할때는 t_g[3]+g[5] 와 t_g[2]+g[4]+g[5] 와 t_g[1]+g[4]+g[5] 세개중 하나를 고르게 되고,

6번째를 고려할때는 t_g[4]+g[6], t_g[3]+g[5]+g[6], t_g[2]+g[5]+g[6] 세개중 하나를 고르게 되죵

kwr0113 3년 전 0

아아... 이해했습니다 친절한 설명 감사합니다 ㅜㅜ

수정한 코드는 n번째 잔을 무조건 마시는 조건 하에 두단계 전의 잔을 마시는 경우를 추가했거든요

두단계 건너뛰는 부분을 추가해주는게 포인트였던거 같습니다 감사합니다

# 2156.PY

n = int(input())

grape = [int(input()) for _ in range(n)]
t_grape = [0 for _ in range(n)]

t_grape[0] = grape[0]

if n > 1:
    t_grape[1] = grape[0] + grape[1]
if n > 2:
    t_grape[2] = grape[2] + max(grape[0], grape[1])

for i in range(3, n):
    t_grape[i] = grape[i] + max(t_grape[i-2], grape[i-1] + t_grape[i-3], grape[i-1] + t_grape[i-4])

print(max(t_grape))

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

문제

문제

출처

ICPC

와인을 마시지 않는 경우가 왜 필요한가요?

kwr0113 3년 전 1

a99azaz 3년 전 3

pmn0001 3년 전 1

kwr0113 3년 전 0

pmn0001 3년 전 4

kwr0113 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말