* 위에 0이라고 되어 있는 부분은 중간에 이 길이 아니라고 포기하는 경우로 보입니다.
그런데 이 경우 0은 많이 약합니다. 1 100 1 이라고 주어지면 1, 100, 가다가 1을 못가니까 포기하는데 1 + 100 + 0 이 되니까 최대값이 됩니다.
(정확히 위 소스에서 이렇게 되는지는 모르겠지만 중간 포기용으로 0이 위험하다는 예입니다.)
그래서 이 문제의 경우는 -3,000,000 보다 작은 어떤 수를 해야지 어떤 경우에도 양수로 못나옵니다.
* 30번째 라인은 memoization 을 위한 것으로 보입니다. 그런데 변수인 i 만으로 정해지는 것은 아니고 b, bchk에 의해서도 결과가 바뀌기 때문에
val 의 인자가 이 3가지를 모두 저장해야할 것 같습니다. b 대신에 이전에 몇 계단을 연속으로 왔는지를 넣으면 0, 1, 2 를 가질 것이고
그러면 val[i][b] 정도로 저장할 수 있을 것 같습니다.
* 많은 경우에 이 문제를 푸신 분들은 아래와 같이 푸는 것 같습니다.
val[i] = max( (ad[i-1] + val[i-3]), val[i -2]) + ad[i]
* 디버깅은.... 47줄을
int aa = calc(ad, val, i + 1, true);
int bb = calc(ad, val, i + 2, false);
System.out.println( "turn " + i + " " + bChk + ", +1 " + (aa + ad[i]) + ", +2 " + (bb + ad[i]) + " " + ad[i]);
return val[i] = Math.max(aa, bb) + ad[i];이렇게 바꿔서 했습니다. (디버깅은 노가다와 집착이 아닌가 합니다. ㅠㅠ)
* 30~33라인 지우고 0을 충분히 작은 수(-10000. 원래는 더 작은 수로 해야하지만.. )로 해서 81이 나오는 것은 확인했습니다.
Success #stdin #stdout 0.07s 2184192KB turn 7 true, +1 -9995, +2 -9995 5 turn 6 true, +1 -9975, +2 21 20 turn 4 true, +1 -9980, +2 41 20 turn 6 true, +1 -9980, +2 21 20 turn 5 true, +1 22, +2 -9999 1 turn 3 true, +1 42, +2 23 1 turn 1 true, +1 -9999, +2 43 1 turn 6 true, +1 -9980, +2 21 20 turn 5 true, +1 22, +2 -9999 1 turn 3 true, +1 -9999, +2 23 1 turn 5 true, +1 -9999, +2 -9999 1 turn 7 true, +1 -9995, +2 -9995 5 turn 6 true, +1 -9975, +2 21 20 turn 4 true, +1 -9979, +2 41 20 turn 2 true, +1 43, +2 61 20 turn 0 true, +1 63, +2 81 20 81
ssifood 5년 전
전역 boolean 상수 bChk로 전칸보다 +1하면 True하고
+2이하면 false를 만들어서
+1+1 을 배제하려고 했는데, 이 소스가 어렵습니다.;;
dp배우는 과정인데 백준 예제는 통과하고
반례는
9
20
1
20
1
20
1
20
5
1
이것을하면 86으로나옵니다.
correct anwser : 81이나와야합니다.
그리고 이소스 디버깅하는데 어렵네요;;;
디버깅 팁이나, 이것은 어떻게 고쳐야 할지 살려주십시오.
징징쩔죠?