[Level03] 경주로 건설

[sangmandu]

경주로 건설 문제입니다.

문제에 오류가 있습니다. 여기에 어떤 오류인지 자세히 적어놓았습니다.

오류를 해결할 수 있는 풀이로 풀어보고 싶었는데 2시간 정도 고민하다가 포기합니다. 다른 분들은 혹시 해결하실 수 있을까 해서 도움을 요청해요!!

아마 문제 오류를 먼저 보면 제 풀이랑 비슷하게 풀지 모르니, 먼저 풀어보시고 한번 오류까지도 해결할 수 있는 풀이를 고민해보시길 추천해요.

[RockMiin]

풀이를 살펴봤는데 간결하게 잘 짜신 것 같은데 방향의 순서에 따라서 오류가 나는 이유는 잘 모르겠네요. 우선 제 방식대로 풀이는 올렸습니다 !

[sangmandu]

풀이를 살펴봤는데 간결하게 잘 짜신 것 같은데 방향의 순서에 따라서 오류가 나는 이유는 잘 모르겠네요. 우선 제 방식대로 풀이는 올렸습니다 !

그림을 그려서 설명하자면, 깃발이 있는 칸이 도착지점이고, 현재 도착지점에 가기 한칸 전(도착지점 기준 왼쪽칸)에 두 가지 경로가 있다고 하겠습니다. 이 때 도착지점은 E, 전 지점을 P 라고 하면

• 빨간색 경로로 먼저 따지고 파란색 경로를 따지는 경우
  • 빨간색 경로 : E 지점은 3000원으로 최솟값 설정, P 지점은 3600원으로 최솟값 설정.
  • 파란생 경로 : E 지점은 3400원으로 최솟값 보다 높으므로 종료.
• 파란생 경로로 먼저 따지고 빨간색 경로를 따지는 경우
  • 파란생 경로 : E지점은 3400원으로 최솟값 설정. P 지점은 3500원으로 최솟값 설정.
  • 빨간색 경로 : E지점은 3000원으로 최솟값 갱신. P 지점은 3600원으로 최솟값보다 높으므로 종료.

따라서, 어떤 경로를 먼저 고려하냐에 따라 결과가 달라지게돼요. 그래서 move의 방향 순서가 빨간색을 먼저 고려하게 하는 방향이었다면 오답이 뜰것이고 파란색을 먼저 고려하게 하는 방향이었다면 정답을 뜨게 할 것이에요

이해가 좀 되셨나요?? 저는 이 문제점을 파악한 뒤에 해결해보려고 했는데 그것까지는 어렵더라고요

[RockMiin]

친절하게 설명 해주셔서 잘 이해했습니다. 저도 생각 한 번 해볼게요 !