소프티어

2일 동안 dp 방식으로 머리 싸매면서 풀었는데 어떻게 해도 안되길래 뭔가 위쪽 방향에서 합쳐지는 값이랑 왼쪽 방향에서 합쳐지는 값이 같을 때 각 경로 내 최댓값이 다름에도 값을 1개만 저장해주는 게 문젠가 싶어서 dp 말고 bfs로 풀었고 통과했습니다,,

대충 bfs 로 푼 방법 공유

1. 해당 지점까지의 수확량 중 최댓값을 저장할 2차원 배열을 하나 만들고 (이 때 스프링쿨러로 증가된 수확량은 더하지 x)
2. queue에서 뽑은 현재 지점까지의 수확량이 1번에서 만든 2차원 배열에 저장된 지점값보다 작다면 해당 경로는 드롭
3. 오른쪽이나 아래로 뻗은 경로에서 갱신된 수확량이 마찬가지로 1번 배열에 저장된 지점값보다 작으면 해당 경로는 드롭하고 같거나 크면 queue에 넣어주고 1번 배열을 업데이트. 이때 경로의 수확량에는 경로 내 최댓값을 더하지 않고 따로 queue에 넣어줌.
4. N-1,N-1 에선 경로 수확량+경로 내 최댓값 계산해서 정답 계속 업데이트해주기

너무 졸린 상태로 써서 말이 좀 중구난방인데 이해가 잘 안가신다면 코드로 첨부해드리겠습니다...!

저는 이만 12번 반례 마저 찾으러,,,

왜 통과했는지도 모르고 얼레벌레 통과하니까 굉장히 찝찝하네여