seastar105   5년 전

다음과 같이 문제를 수정해주세요 :

지문

도시와 도로의 정보가 주어졌을 때 모든 도시에 대해 각 도시를 거점도시로 지정했을 때 만들 수 있는 패키지 관광 상품의 최대 즐거움을 구하는 프로그램을 작성하자.

->

패키지 상품의 설계에 도움이 되도록 도시와 도로의 정보가 주어졌을 때 모든 도시에 대해 각 도시를 거점도시로 지정했을 때 도달 가능한 도시들의 즐거움의 최대값과 최소값의 차이를 구하는 프로그램을 작성하자.

출력

i번째 줄에는 i번 도시에서 출발하는 패키지 상품 중에서 가장 큰 즐거움을 가지는 패키지의 즐거움을 총 N줄에 걸쳐 출력한다.

->

i번째 줄에는 i번 도시에서 도달 가능한 도시들의 즐거움의 최대값과 최소값의 차이를 총 N출력한다.

-


이 문제는 i번 도시에서 도달 가능한 도시들의 즐거움의 최대값과 최소값의 차이를 출력하는 것을 의도하고 문제를 만들었습니다.

하지만 지문에는 i번 도시에서 출발하는 패키지의 즐거움의 최대값과 최소값의 차이를 요구하고 있습니다. 이는 완전히 다른 문제입니다.

따라서 지문을 의도된 풀이에 맞도록 문제 지문을 수정해야 합니다.

잘못된 문제로 시간을 낭비하신 분들에게 진심으로 사과 드립니다. 진짜 죄송합니다.

seastar105   5년 전

도움을 주셔서 감사합니다. 아래는 해당 내용을 반영한 지문 수정본입니다.

---

당신은 성공적으로 여행사를 운영 중인 CEO다. 새로운 나라에서 여행사를 전개하고자 하는데 이를 위해서 첫 거점 도시를 정해야 한다.

새로운 나라는 $N$개의 도시가 존재하고 각 도시 간에 양방향으로 통행 가능한 $N-1$개의 도로가 존재한다. 어떠한 도시에서 출발해도 도로를 따라 다른 도시로 도착하는 것이 가능하다.

도시는 각각 해당 도시의 즐거움을 나타내는 수 $c_i$가 있다. 이 수가 클수록 즐거운 도시다.

여행사의 주력상품은 패키지 관광 상품이다. 패키지 관광은 거점 도시에서 출발하여 도달 가능한 모든 도시를 방문하는 관광 상품이다.

패키지의 즐거움은 들른 도시 중에서 가장 큰 즐거움을 가진 도시의 즐거움과 가장 작은 즐거움을 가진 도시의 즐거움의 차이다.

재밌는 도시는 몇 번을 들러도 재밌고 재미없는 도시는 몇 번을 들러도 재미없기 때문에 패키지 도중에 한 도시를 여러번 들러도 괜찮다. 

이 나라에는 이상한 제한이 있는데 $i$번 도시에서 출발하는 관광버스는 $i$번 도시에서만 탑승할 수 있으며 $i$번 도시에서 최대 $d_i$만큼 떨어진 도시로만 이동할 수 있다.

이러한 제한 때문에 패키지 설계에 골머리를 앓고 있는 당신은 꼼수를 하나 생각했다. 

$i$번 도시에서 출발하는 관광버스는 해당 도시에 있기만 하면 언제든지 탈 수 있기 때문에 거점으로 삼은 도시에서 출발하는 관광버스에 손님을 태우고 다른 도시로 가서 그 도시의 관광 버스에 손님들을 태우면 더 멀리 갈 수 있는 것이다.

이렇게 버스를 계속 갈아타는 것을 여러번 반복하면 훨씬 더 많은 도시에 갈 수 있다. 

여행사에서 최대한 즐거운 패키지 상품을 만드는 것은 중요하기 때문에 어떤 도시를 첫 거점으로 삼을지 다시 고민에 빠졌다.

도시와 도로의 정보가 주어졌을 때 모든 도시에 대해 각 도시를 거점도시로 지정했을 때 만들 수 있는 패키지 관광 상품의 즐거움을 구하는 프로그램을 작성하자.

---

출력 부분도 아래와 같이 수정되어야 합니다.

---

$i$번째 줄에는 $i$번 도시를 거점 도시로 지정했을 때 만들 수 있는 패키지 관광 상품의 즐거움을 총 $N$줄에 걸쳐서 출력한다.

---

seastar105   5년 전

먼저 의도된 풀이는 정점 i에서 거리가 d_i인 정점들로 전부 유향 간선을 이어주고 새로 만든 그래프에서 SCC로 묶어주고 DP 돌리는 것입니다.

이 의도대로 되려면 지문에서 

"i번 도시에서 출발하는 버스는 i번 도시에서만 탈 수 있다. 그리고 패키지 도중에 들렀던 도시로는 언제든지 다시 돌아갈 수 있고 거기서 다시 버스를 탈 수 있다."

이 조건이 추가된다면 말이 될까요? 정말 죄송합니다.

seastar105   5년 전

위 댓글을 쓰는 도중에 댓글이 달려서 미처 못봤네요. 

"패키지의 즐거움은 ...차이다." 라는 문장을 빼버리는게 더 말이 되는 거 같아요

seastar105   5년 전

패키지에 대한 내용을 다 뺐습니다.


지문

당신은 성공적으로 여행사를 운영 중인 CEO다. 새로운 나라에서 여행사를 전개하고자 하는데 이를 위해서 첫 거점 도시를 정해야 한다.

새로운 나라는 ​$N$개의 도시가 존재하고 도시 간에 양방향으로 통행 가능한 $N-1$​개의 도로가 존재한다. 어떠한 도시에서 출발해도 도로를 따라 다른 도시로 도착하는 것이 가능하다.

도시는 각각 해당 도시의 즐거움을 나타내는 수 $c_i$가 있다. 이 수가 클수록 즐거운 도시다.

이 나라에는 이상한 제한이 있는데 $i$​번 도시에서 출발하는 관광버스는 ​$i$번 도시에서만 탑승할 수 있으며 $i$​번 도시로부터 최대 $d_i$​만큼 떨어진 도시로만 이동할 수 있다.

$i$​번 도시에서 출발하는 관광버스는 해당 도시에 있기만 하면 언제든지 탈 수 있기 때문에 거점으로 삼은 도시에서 출발하는 관광버스에 손님을 태우고 다른 도시로 가서 그 도시의 관광 버스에 손님들을 태우면 더 멀리 갈 수 있다.

이렇게 버스를 갈아타는 것을 여러번 반복하면 거점 도시에서 출발하는 버스만 이용하는 것보다 훨씬 더 많은 도시에 갈 수 있다.

거점 도시를 정하는 데에 있어서 중요한 것은 거점 도시에서 도달 가능한 도시들의 ​즐거움의 최대값과 최소값의 차이이다.

도시와 도로의 정보가 주어졌을 때 모든 도시에 대해 각 도시를 거점도시로 지정했을 때 도달 가능한 도시들의 즐거움의 최대값과 최소값의 차이를 구하자.

입력은 변경사항 없습니다.

출력

$i$​번째 줄에는 ​$i$번 도시에서 도달 가능한 도시들의 즐거움의 최대값과 최소값의 차이를 총 ​$N$줄에 걸쳐 출력한다.

seastar105   4년 전

@startlink

위 지문대로 수정 가능할까요?

startlink   4년 전

수정했습니다.

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