ssifood   7일 전

전역 boolean 상수 bChk로 전칸보다 +1하면 True하고

+2이하면 false를 만들어서  

+1+1 을 배제하려고 했는데, 이 소스가 어렵습니다.;;

dp배우는 과정인데 백준 예제는 통과하고 

반례는

20

1

20

1

20 

20

5

1

이것을하면 86으로나옵니다. 

correct anwser : 81이나와야합니다.

그리고 이소스 디버깅하는데 어렵네요;;;

디버깅 팁이나, 이것은 어떻게 고쳐야 할지 살려주십시오.

징징쩔죠?

seico75   7일 전

* 위에 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

indioindio   7일 전

백0원급 솔루션이라고 생각합니다.

ssifood   6일 전

살려주셔서 감사합니다. 코린이 부끄럽습니다.

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