cbs0615   8년 전

//안녕하세요 아까전에 질문 올렸던 사람입니다. 아까 전에 지적해 주신 문제는 해결하였습니다. 1번의 경우에 문제가 생겼는데 OOOXO인 상황이 안생기기 위해서  OXO인 경우 Sums[i-3][2]가 최대 합 Sums[i-3][0]인 경우, 그 전까지의 최대합을 써서 ..XOXO로 처리했었는데 주신 예시를 보니 제가 Sums[i-3][1], 즉 XOOXO의 경우를 뺐었습니다. 따라서 아까전 문제에서 다음과 같이 수정을 하였습니다.

Sums[i][j]  : i번째 포도주 잔을 포함하여 i번째 까지 포도주 양의 최대 합, 마지막으로 j번 연속. ( Sums[i][0]은 i번 째까지 중에서 포도주 양의 최대 합을 저장하고 있는 공간입니다)

Sums[i][j]는 다음과 같은 점화식을 만족한다는 가정을 세웠습니다.

1. Sums[i][1]는 마지막에 OXO로 끝나는 경우로
만약 Sums[i-3][0] ( i-3번 째까지 최대 합, i-3번 째를 포함하지 않을 수 있음)이 Sums[i-3][2]와 같다면 OOOXO 인 상황이 발생하여 그 전 까지의 최대합 Sums[i-4][0]과 1번만 연속하여 끝나는 Sums[i-3][1]을 비교하여 큰 값을 temp로 하여, temp + wines[i] + wines[ i-2] 로 설정하였습니다.

2. Sums[i][2]는 마지막에 XOO로 끝나는 경우로 Sums[i-3][0] + wines[i] + wines[i-1] 로 설정하였습니다.
(wines 는 wine양을 저장하고 있는 배열입니다, maxSum은 최대합을 구하기 위해 만든 변수 입니다.)

아직 틀린 답안으로서, 조언이 필요합니다 여러분들~

indioindio   8년 전

10
977
200
517
851
23
662
880
815
26
214

4254 대신 4127을 출력하네요.

8까지의 4040 + 214가 아닌 9의 maxSum[9][1](3913) + 214를 출력한 것 같네요.

cbs0615   8년 전

늦은 시간인데도 정말 감사합니다. 알고리즘에 문제가 있었습니다. 감사합니다 ~!!

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