ddolgu14   9달 전

안녕하세요. 백준 알고리즘에 처음 글 써보는 뉴비입니다. 

다름이 아니라 최근에 dp를 공부하고 있는데 많이 어려워서 도움이 필요합니다 여러분들~

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]을 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   9달 전

5

1

2

3

1

3

일 때 2+3+3=8 대신에 1+3+3= 7을 출력하네요. 첫번째를 무조건 마시게 되는 것 같습니다.

ddolgu14   9달 전

정말 감사합니다

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