lyzqm   2년 전

1.png

미리 전처리로 누적합을 구해준 다음에 M번마다 위의 합중 최솟값을 구해줬습니다.

A집과 B집이 1칸 차이나는 경우에는 따로 예외처리를 해줬는데 어디서 틀린지 모르겠습니다

빠진 부분이 있는지 알려주시면 감사하겠습니다


chogahui05   2년 전

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


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

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

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


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

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

chogahui05   2년 전

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

그것도 아닙니다.


lyzqm   2년 전

아아

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

감사합니다

chogahui05   2년 전

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

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

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


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

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

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

chogahui05   2년 전

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

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

lyzqm   2년 전

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

ainch96   2년 전

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

chogahui05   2년 전

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

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

chogahui05   2년 전

@lyzqm

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

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

lyzqm   2년 전

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

chogahui05   2년 전

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

ainch96   2년 전

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

ainch96   2년 전

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

chogahui05   2년 전

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

chogahui05   2년 전

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


문제 상황을 보니까요..

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

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


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

저는요..


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

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

댓글을 작성하려면 로그인해야 합니다.