밑에 주석친 SPFA 풀이는 답은 나오는데 시간초과가 뜨고,  DP 문제임을 확인하고 DP로 풀려니 틀립니다.

몇개 넣다가 도저히 안될것 같아 랜덤값 생성하는 코드로 랜덤값들 만들어서 넣으니까 반례는 파악했습니다.

문제는 반례는 파악했는데 아직 어떻게 고쳐야 할지 감이 안잡히네요. 일단 패스할랍니다. DP 너무 어렵네요.

풀었습니다.

그래도 데이터 한두개 넣은게 아니라 넣은 데이터들 뿌립니다.

1 1
100

답 100

5 5
0 1 1 1 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1

답 8

1 2
9 9

답 18

2 1
9
5

답 14

3 3
0 0 100
1 1 0
1 1 0

답 100

랜덤값 생성기로 만들어 넣어본 데이터들입니다. 너무 길어서 메모장으로 올립니다.

BOJ11048_Input_1.txt

답 17983

BOJ11048_Input_2.txt

답 72241

BOJ11048_Input_3.txt

답 149508

BOJ11048_Input_4.txt

답 113302