코너 케이스 하나는 잘 처리하셨는데..

상당히 매력적인 함정에 걸려드셨네요. 이 문제 누가 낸 건지 모르겠는데.. 

새로운 길로 왔다가 엄청난 코스트 때문에 다시 돌아가야 하는 경우도 있습니다.

lyzqm님 코드에 따르면 새로운 길을 거쳐 갔다가 100짜리를 밟아야 최적의 cost가 되어 버리는데..

실제로는 5에서 6으로 가지 않는게 최적입니다.

0 - 1 - 6 - 1 - 2 - 3 - 4 - 5 이렇게 가는 게..

그렇다고 끝에만 처리하면 되냐고 물어보신다면 

그것도 아닙니다.

아아

다시  새 집쪽으로 가는 경우가 있군요

감사합니다

아. 이럴수가.. 2번째 답변은 무시해 주세요..

갈래길을 만나면 왔던 길을 되돌아가거나 두 길 중 하나로 갈 수 있다.. 여서..

이 경우가 반례가 될 거 같네요..

왜 이렇게 문제가 O(n^3)으로 풀릴 거 같은 느낌이 들 정도로 왜 이렇게 하드코어 하지? 라고 생각했는데..

숏코딩이 있는 걸 봐서는 어렵지 않을 거라 생각했고 자세히 읽어보니 갈림길을 만나거나

막다른 길을 만나면 방향을 틀어버릴 수 있다. 는 조건이 깔렸네요.

접근 방법은 옳은 거 같으니까

몇 가지 가짓수만 더 판단해 주시면 될 거 같네요. 아마 3가지 정도? 있을 겁니다.

넵 풀어보다가 또 모르면 질문드릴께요 ㅋㅋ

저는 자꾸 틀려서 나올 수 있는 경우를 수형도로 그려봤더니 8가지 정도 나오더라고요. 모든 경우 다 처리해주니 맞았습니다. 출제자의 말에 따르면 8가지 중에 중복되는거 줄이면 경우는 적어진다고 들었지만 적어도 3개 보다는 많은경우가 있는걸로 압니다.

다시 그려보니 4가지 정도 나오네요..

그런데 이렇게 풀면 9%에서 틀리는 걸로 봐서는 더 있는 거 같네요.

@lyzqm

아. 이거 어이없게 틀렸었네요. ㅡㅡ

경우 수만 잘 따져보아요. 4가지 맞아요. 맞출 수 있어요. ㅡㅡ

오 푸는거 까먹고있었는데 다시 도전해보겠습니다!

스티커 문제보다 쉬우니 도전해 보세요.

@chogahui05 혹시 boj 슬랙에 있으신가요?

여쭤볼께 있는데 ... 지금 데이터가 틀린 상황이거든요. 틀린 데이터에 맞게 예외처리 해서 맞으신건가요?

거리 차이가 1인 경우에요.. ntopia님 말씀대로요.

이게 정확하게 말하면 갈래길하고, 막다른 길을 어떻게 정의하느냐에 따라서 달라지는 문제긴 한데요.

문제 상황을 보니까요..

일단 사람이 가는 방향이 있으니까. 최소 삼거리 이상은 되어야 선택할 수 있는 가짓수가 2가지 이상이 되어서.

(#) 갈래길을 만나면 두 길중 하나로 가거나, 오던 길로 되돌아갈 수 있다.

(#)이라는 행위를 할 수 있어서 그렇게 정의를 했어요. (갈림길 = 3거리, 4거리, ...)

저는요..

막다른 길은. 내가 가던 방향으로 계속 쭉 갔을 때, 더 이상 갈 수 없는 경우로 정의했는데요.

힌트의 1번째 그림에서는. 5에서 6번방향으로 간 경우, 6번에서 더 이상 오른쪽으로 갈 수 없으니.. 이걸 막다른 길로 정의했습니다.