도움을 요청 드립니다.

  • shoulder4
    shoulder4

    문제가 어려워서 ㅠ.ㅠ 아무리 생각해도 잘 몰라서
    알고리즘상 힌트를 부탁드립니다.

    N개의 도시에 N개의 Job이 있음
    각 도시를 방문할때는 교통비를 지출하고
    Job을 수행합니다.
    이때 수입이 발생합니다.

    도시들은 Circular로 연결되어 있습니다.
    5개의 도시가 있다면 다음과 같이
    1-2-3-4-5-1 식으로 돌아갈 수 있습니다.

    마지막으로 도시 방문 순서가 주어집니다.
    5,2,3,1,4 식으로... 반드시 이 순서는 지켜져야 하며 1~N의 도시가 한번씩 나옵니다.

    도시를 선택하여 일을하여 수입을 발생시킬 수있고 선택안하고 가만히 있을 수도 있습니다. 선택안하면 다음 번에는 Job이 없어져 이후 가더라도 수입을 얻을 수 없습니다.

    처음 위치는 1번도시에 있고 모든 Job을 마치고 1번도시로 돌아와야 합니다.
    도시 방문 순서가 a,b,c,d라면
    1 -> a -> b->c ->d -> 1 순으로 와야 합니다.
    만일 a가 1이면 1 -> 1이므로 교통비가 들지 않습니다.

    예를 들어
    3 <-- 도시가 3개 있으며 1,2,3
    2, 6, 8 <-- 수입 : 1번 도시에서 일을 하면 2를 얻음
    2, 6, 1 <-- 교통비 1번도시에서 2번도시로 갈때 2를 지출
    <-- 2번도시에서 3번도시로 갈때 6을 지출
    <-- 3번도시에서 1번도시로 갈때 1을 지출
    1,2,3 <-- Job이 있는 도시의 순서

    라고 할때

    1,2,3순서로 다 방문할때는

    2(수입) -> 2 이동(교통비 2, 수입 6)
    -> 3으로 이동 (교통비 3(2->1->3으로 이동하면 더싸기 때문), 수입 8)을 얻고 마지막으로 1로 이동시 (교통비 1)이 듭니다.

    이를 알고리즘으로 구현 하고자 하면
    다음과 같이 도는데,
    city의 개수가 최대 10만이라서
    동적 계획법을 사용하가기 어렵네요
    10000이하일때만 메모할수는 있는데
    다른방법은 없을까요???

    function(step, curCity)
    {
    if(step == N)
    return CalcFee(curCity,1)

    if(curCity == 방문순서[step+1])
{
    return function(step+1, curCity) + 수입[curCity]; 
}

nextCity = 방문순서[step+1];
return max(
    function(step+1, curCity) , 
    function(step+1,nextCity)-CalcFee(curCity, nextCity) + 수입[nextCity])

    }


    10년 전
7개의 댓글이 있습니다.
  • 일루
    일루

    문제 설명대로라면 같은 구간을 왔다갔다왔다 해서 총 3번 이상 가는 것은 무조건 손해가 됩니다. 이 성질을 이용하면 어떨까요?


    10년 전 link
  • Neon
    Neon

    그냥 도시를 지나치는 것은 방문으로 간주하지 않는 것 같군요.

    주어진 도시 방문 순서를 지켜야만 한다면 다음과 같이 정의해 보세요.

    D[x] := 방문 순서 중 x번째 도시에 도착했다! 라고 가정했을 때 최대 수익.

    근데 이렇게 짠다 가정하더라도 계산량이 O(N^2)이라 빨리 나올 것 같지는 않네요.


    10년 전 link
  • Neon
    Neon

    그렇다고 N^2 계산을 안할수도 없을 것 같은게, 수입 값이 높은 경우에는 무조건 이동하는 편이 좋고, 그렇지 않더라도 중간에 들러 일할 수 있는 상황이면 무조건 이동하는 편이 좋기 때문에... 여튼 이걸 더 줄이려면 뭔가 조건을 찾아 상태공간 검색 수를 줄여야 하는데 아이디어가 별로 없네요.

    일루님이 말씀하신 아이디어는 중간에 발생하는 수익 때문에 성립하는지 의문이 좀 들구요...


    10년 전 link
  • 일루
    일루

    방문 순서를 지키지 않아도 되는것 같아요. 방문 순서를 지킨다면 단순한 최단거리 문제가 되지 않을까요?


    10년 전 link
  • shoulder4
    shoulder4

    모두 도움을 주셔서 감사합니다.

    방문 순서는 지켜야 하고, Skip을 할지 말지가 관건입니다.
    방문 순서를 지킨다하면 단순 최단거리 문제가 되는지 잘 이해가 안되네요. 설명을 부탁드리겠습니다.


    10년 전 link
  • shoulder4
    shoulder4

    해결하였습니다 N^2.. 동적 계획법과 비슷한데 거꾸로 계산하면 쉽게 해결이 가능하네요..

    f(n,m) = max(f(n+1, m) , f(n+1, list(n+1)) + imcoming(list(n+1)) - fee(m -> list(n+1)) )

    n이 for loop의 step이라 N


    10년 전 link
  • shoulder4
    shoulder4

    2^N의 노드 개수를 최대 개수가 (N+1 * N) /2이 되네요
    이를 거꾸로 계산하면 되네요.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.