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이하일때만 메모할수는 있는데
다른방법은 없을까요???
그렇다고 N^2 계산을 안할수도 없을 것 같은게, 수입 값이 높은 경우에는 무조건 이동하는 편이 좋고, 그렇지 않더라도 중간에 들러 일할 수 있는 상황이면 무조건 이동하는 편이 좋기 때문에... 여튼 이걸 더 줄이려면 뭔가 조건을 찾아 상태공간 검색 수를 줄여야 하는데 아이디어가 별로 없네요.
일루님이 말씀하신 아이디어는 중간에 발생하는 수익 때문에 성립하는지 의문이 좀 들구요...
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)
}
11년 전