method(A, start)의 논리를 따라가보면,

1. d[start]에 저장된 값이 있으면 이를 반환.

2. for문을 돌리며 오늘 이후로 일을 수행할 수 있는 경우를 따져보는데, d[i]에는 i일에 일을 하는 경우 최대 금액을 저장.

3. i=start~N에 대해 d[i]의 최댓값을 반환.

이 됩니다.

그런데 2번에 따르면 d[i]에는 'i일에 일하는 경우만을 확인한 값'이 저장되고, 1번과 3번에 따르면 d[i]가 0일 경우에 한해서는 for문을 돌며 'i일 이후로 얻을 수 있는 최대 금액'을 반환하게 됩니다.

이후 같은 start 값에 대해 method(A, start)가 호출될 경우, d[i] 값을 반환하게 될 것입니다. 즉, 같은 start 값에 대해 처음과 두 번째 이후 각각 다른 반환값을 줄 수 있게 됩니다.

이에 대한 반례는

4

2 800

1 900

2 200

1 900

입니다.

(method(0)

-> i=0 -> method(2)=900 -> d[0]=800+900

-> i=1 -> method(1) -> method(2)=200 -> d[1]=900+200)

반례는 아래와 같습니다.

코드의 구조적인 문제를 말씀드리자면 method(A,start)는 d[start]의 값을 계산하고 반환하는 함수이므로, 함수 내부에서도 d[start]에 대한 갱신만이 일어나고 반환도 항상 d[start]를 해야 의미상 옳습니다. 하지만 이 코드에서는 i >= start인 모든 i에 대애 d[i]를 직접 갱신하고 있어 이 의미가 퇴색되고, 마지막에도 d[start]가 아닌 max를 반환하고 있습니다.

d[start]의 의미를 먼저 명확히 해서 이 함수가 항상 d[start]에 대한 계산만을 수행하도록 하고, 다른 i에 대해서는 method(A,i)를 호출해서 값을 받아오기만 하고 갱신은 직접 하지 않도록 코드의 구조를 만들어보시기 바랍니다.

두분다 너무 감사드립니다!!