ntopia   3년 전

만약 입력으로 주어지는 Aj, Bj 가

| Aj - Bj | == 1  을 만족하는 경우에는

0번  --->  min(Aj,Bj)번 ---(새 길 이용)---> max(Aj,Bj)번 ---> N번

이런 식으로 이동하는 것이 최적일 수 있는데

이 경우를 고려하면 틀렸습니다를 받고, 이 경우를 고려하지 않으면 맞았습니다를 받네요.

데이터가 틀린 것이 아닐까 합니다...

ntopia   3년 전

출제자 분에게 알림을 걸어보겠습니다... @qdqd

ntopia   3년 전

그림을 그려 설명해보자면


show1.png

요런식으로 빨간색 길이 새롭게 생기는 길이라고 해봅시다. 그렇다면


show2.png이렇게 연두색 경로로 가는 것이 답의 후보 중 하나가 될 수 있습니다.


하지만 이 연두색 경로를 고려하면 틀리고, 고려하지 않으면 맞아요.

chogahui05   3년 전

어떻게 아셨대요.. 분명 수형도 그려봐도 이상이 없었는데.. 자꾸 9%에서 나가길래 이상하다 싶었네요.

1주 전에 분명 풀었는데 발견 못해서 틀렸네요.



ainch96   3년 전

생각도 못했네요;; 문제 데이터를 살펴봤을 때 ai + 1 == bi 인 경우가 있네요. 출제자에게 의논해서 수정하도록 하겠습니다. 

qdqd   3년 전

넵. 여기 출제자입니다. 엉엉.

그림1.png

코드를 보니 위 그림과 같이 이동하는 경우에서 A~A+1까지의 거리를 빼주지 않아서 

len(A~A+1)이 총 거리에서 제외되지 않는 경우가 생겼습니다.


지금 코드와 output을 수정해서 백준님께 보내드렸습니다.

잘못된 답을 만들어 많은 분들의 시간을 낭비하게 한 점 죄송합니다.

ntopia   3년 전

궁금한게 있는데,

저 경우에는 A+1 에 갈림길이 없으니 왔던길로 돌아갈 수 없는게 아닌가요?

사실 '갈림길이 있는 곳' 이라는 것도 degree 가 3 이상인 정점 이라고 해석했는데, 이것도 맞는 해석인지 궁금합니다

chogahui05   3년 전

저 같은 경우

인호는 길을 따라 걸으며 갈래길을 만나면 두 길중 하나로 가거나, 오던 길로 되돌아갈 수 있다. 그리고 막다른 길에 다다르면 되돌아간다.

이거를 이렇게 해석했습니다.


(1) 길을 따라 걸으며

= 일단 자기가 가던 방향으로 가는데.


(2) 갈래길을 만나면

= degree가 3 이상인 정점을 만나면


(3) 두 길 중 하나로 가거나

= 내가 보고 있는 방향을 기준으로 해서, 뒤에 있는 방향에 있는 길을 제외한 두 길 중 하나로 가거나.


(4) 혹은 오던 길로 되돌아 갈 수 있다.

= 그냥 유턴할 수 있다.


예를 들어서 예제 1 같은 경우 2번에 도착한 순간에 2->3 방향을 보고 있었을 때,

2번 도시에서, 새길로 가는 경우가 있고, 2->3으로 가는 경우가 (3)에서 말한 두 길이라고 해석했고요.

오던 길로 돌아가는 경우는 2->1로 되돌아 간다고 해석했습니다. 출제진 분들의 의도가 어떤 건지는 잘 모르겠지만요.

lyzqm   3년 전

@qdqd

재채점 결과가 이상한것같습니다

문제 출제자님 다시한번 확인해주시면 감사하겠습니다

qdqd   3년 전

@lyzqm

넵 제가 갈림길 조건을 고려를 안하고 A+1에서 방향을 수정할 수 있는 코드를 백준님께 수정코드라고 제출했습니다. ㅠㅠㅠ

조건에 맞추어 저 방식으로 이동하게 되면

가게 -> A -> 새집 -> B -> A -> N 순서로 이동하는 것이 맞습니다.

해당 경우를 바꿔주고 길이가 1인 경우만 다시 예외처리를 해 수정메일을 보냈습니다.


그리고 갈림길의 조건은 그냥 새집과 연결된 집이라고 의도하고 문제를 제출했습니다.

A < B = N인 경우 B(=N) 지점도 갈림길과 동일하게 생각했슨데요,

문제에서 새로 만드는 길과 바로 연결된 집에서만 방향을 바꿀 수 있다고 정정하겠습니다.


ㅠㅠㅠㅠ 제가 부족해서 계속 여러 분들의 도움을 받게 되네요...

문제점 발견해주시고 알려주신 많은 분들께 죄송하고 감사드립니다.

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