아 진짜 돌아버리겠네...제발...누가 살려줘

제발 누가 살려줘...

아 왜 틀렸는지 알아버렸습니다...드디어...

제 방법은 기본적으로 그리디 알고리즘이었네요.

당장 다음 수에서 좋을 선택 밖게 안 하기 때문이죠...

당장 다음 수에서는 손해 보지만, 길게 봤을 때 이 노드를 지금 거치지 않음으로 더 큰 이득을 볼 수 있는 상황이 있을 수도 있네요.

후.............................................

쨌든 진전이 있어서 시원하네요

크흑흑흑....해결...해방...

위에서 말한 왜 틀렸는지에 대한 이해가 좀 더 정확해져서,

혹시 나중에 이 글을 보게 될 누군가(그게 내가 될 수도... 사람은 망각의 동물이라고...)를 위해서,

그리고 내 생각을 더욱 견고하게 굳히기 위해서,

부연설명을 더 해봅니다.

"당장 다음 수에서는 손해 보지만, 길게 봤을 때 이 노드를 지금 거치지 않음으로 더 큰 이득을 볼 수 있는 상황이 있을 수도 있네요."

이런 경우가 발생하는 이유를 생각해보니, 단순히 dp[state] = cost, last_city로 저장하는 경우,

이 state에 이르는 수 많은 경로 중에서, 이 state까지만 봤을 때 최적의 답을 제시하는 친구만 저장하는 것이다.

근데, 내 이해가 부족해서일 수도 있는데, 조금 이상하다. 

dp[state][last_city]로 저장해도,

어떤 의미에서는 이 state까지만 봤을 때 최적의 답을 제시하는 경우를 저장하는 것이다.

다만 이 state까지 오는 경로 중에서 마지막 방문한 도시의 위치에 대해서만 확장해서 저장하는 것이다.

dp[state = s][last_city = lc]에 대해서도 수많은 경로가 있을 수 있는데, 왜 수 많은 경로에 대해서는 압축해서 최적값만 적어도 되는 것일까?

여기서 핵심은 "그래서 현재의 decision에 영향을 끼치는가"인가 인 것 같다.

어떻게 왔든, 중요하지 않다. 하지만 만약 "어떻게 왔든"이 현재의 판단에 영향을 끼친다면 얘기가 달라지는 것이다.

그래서 마지막에 방문한 도시만은 상태에 추가해야 되는 게 맞는 거다. 마지막 방문한 도시는 현재 상태에서 출발점을 결정하고, 출발점은 다음 이동비용을 영향을 끼친다.

상태를 정의할 때는, 항상 판단에 필요한 모든 정보가 담겨 있어야 한다. 가 결론이 되는 것 같다.

충분하다면, "근시안적인" 판단을 해도 되는 것이다.

"근시안적인" 판단을 해서 문제가 발생하는 것이 아니라, 불충분한 정보로 판단을 했기 때문이다.

사실 어떻게 보면 같은 말이기도 하고...

음, 이걸 굳이 구분(?)하려고 한 이유는, 문제를 풀 때 "근시안적인" 판단을 하면 안 된다는 느낌은 뭔가 절망적이고 ㅅㅂ어떻게 풀지의 느낌을 준다면,

현 단계의 판단을 하는 데 부족한 정보가 뭐지?를 생각하는 건 좀 더 건설적인 방향으로 도움이되는 것 같아서 적어봅니다.

후, 좋았어. 

아니면 말고