7

1

10

1

10

1

10

1

이면 32를 출력해야 하는데 (1, 10, 10, 10, 1) 23을 출력하네요(1, 10, 10, 1, 1?)

아직 자세히 보지는 않아서 논리 자체의 문제인지 코드 상의 오류인지는 잘 모르겠네요.

count 가 꽉 차지 않았으면 무조건 더하도록 하셔서 그런 것 같네요

위의 예시에서 보면 1, 10, (1), 10, 1, (10)  (괄호안은 건너뛰었다는 의미)이 되어버리는데 사실은 1, 10, (1), 10, (1), 10

이 되어야 최대값에 도달할 수 있을 것 같네요

아 그렇군요... 생각해보니 제 알고리즘으로 접근하면 안되네요...ㅠㅠ

이문제는 어떻게 접근해야 하나요??제가 dp를 잘몰라서 어떻게 풀어야 할지 모르겠어요...ㅠㅠ

음 dp에 익숙치 않다고 하셨으니 우선 일반적인 풀이법에 대해서 설명드릴게요.

f(pos)를 pos까지 왔을 때, 최대로 마실 수 있는 와인의 양이라고 하겠습니다. (꼭 pos의 와인을 마실 필요는 없음.) (이 f함수가 어떻게 이 값을 구하는 지는 모르겠으나 마술같이 잘 구해준다고 합시다.)

그럼 이제 효주가 n의 위치에 있을 때 마실 수 있는 와인의 최대양을 알아보겠습니다.

n-3, n-2, n-1, n 위치가 이렇게 있다고 하면,

효주는 f(n-3) (: n-3까지 왔을 때의 최대값) + n-1 + n의 와인을 마시거나, (f(n-3)이 n-4, n-3을 마신 후의 최대값일 수도 있으니 n-2는 마실수가없죠)

f(n-2) + n의 와인을 마시거나

f(n-1)까지 마시고 n은 안 마실수도 있죠.

 그럼 n까지의 최대값은 max( f(n-3) + wine[n-1] + wine[n],  f(n-2) + wine[n],  f(n-1) )이 됩니다.

근데 f의 정의가 pos까지의 최대값이라고 하였으니, f(n) = max( f(n-3) + wine[n-1] + wine[n],  f(n-2) + wine[n],  f(n-1) ) 꼴의 점화식이 됩니다.

(물론 f(0) = 0, f(1) = wine[1], f(2)= wine[1]+wine[2] 처럼 적절한 초기조건이 있어야 겠죠)

이 함수는 답을 아주 잘 구해줍니다.

다만, f(10)을 구한다고 할 경우, f(7), f(8), f(9)를 구해야 하는데 f(9)를 구하기 위해서는 f(6), f(7), f(8) (두 개나 겹치네요)를 구해야 합니다.

그래서 이 때 dp가 필요한 것 입니다.

별 게 아니라, 별도의 테이블에 f(k)의 값을 적어두고, f(n)를 계산하기에 앞서서 f(n)이 테이블에 있다면 (tbl[n] != -1) 계산하지 않고 tbl[n]을 반환하고, 계산결과가 없다면 f(n)의 결과값을 tbl[n]에 기록한 다음, tbl[n]을 반환하면 됩니다.

물론 위와 같은 재귀적 풀이는 함수호출 때문에 조금 느릴 수도 있고, 메모리가 부족할 수 도 있습니다.

그때는 tbl[pos]를 pos까지 왔을 때, 최대로 마실 수 있는 와인의 양이라고 하고 tbl[n] = max ( tbl[n-3]....)처럼 식을 세우고,

포문으로 i = 0부터 시작해서 tbl[i]를 채워나간다면 됩니다.

1 2 3 더하기라는 문제가 위의 재귀적 방식으로 풀기 괜찮은 dp문제이니 (사실 이 문제는 범위가 작아서 11까지 밖에 없어서 dp없이도 풀 수 있었던 것 같습니다.) 한 번 풀어보시는 걸 추천드립니다.

친절한 설명 감사합니다!!  말씀해주신데로 코딩을 한번 해볼께욥... 

새해복 많이 받으셔요.ㅎㅎ

새해 복 많이 받으세요 ~