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은 최대합을 구하기 위해 만든 변수 입니다.)
cbs0615 8년 전
안녕하세요. 백준 알고리즘에 처음 글 써보는 뉴비입니다.
다름이 아니라 최근에 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은 최대합을 구하기 위해 만든 변수 입니다.)
틀린 코드로, 어떤 부분에서 틀렸는지 힌트를 주시면 정말 감사하겠습니다.