문제 링크
- http://icpc.me/5466
문제 출처
- 2009 IOI Day2 4번
사용 알고리즘
- Segment Tree
- DP
시간복잡도
- O(n log n)
풀이
2009년 국제 정보 올림피아드 문제입니다.
풀이에 앞서 몇 가지 변수를 정의하도록 하겠습니다.
- l[x] : x번째 시장의 위치
- m[x] : x번째 시장에서 얻을 수 있는 이득
몇 가지 단계로 나누어 풀이를 해봅시다.
subtask 1. n≤5,000 / 같은 시간에 최대 1개의 시장 개최 (15점)
문제 해석 시간을 포함해서 이 서브테스크를 푸는데는 30분이 걸렸습니다.
dp[i] = i번째 시장까지 갈 때 최댓값
으로 정의하고, 시장의 순서는 시간 순으로 정렬해줍시다.
강을 거슬러 올라갈 때는 미터당 U달러, 반대의 경우에는 D달러가 소요됩니다.
현재 방문해야할 시장의 번호를 i, 이전에 방문했던 시장의 번호를 j라고 정의합시다. l[i] > l[j]라면 이동에 소요되는 비용은 d * (l[i] - l[j])
입니다. 반대의 경우는 u * l[j] - l[i]
입니다. 이를 통해 아래와 같은 점화식을 세울 수 있고, O(n2)만에 점화식을 모두 채울 수 있게 됩니다.
dp[i] = max{ dp[j] - |l[i]-l[j]| * (l[i]<=l[j]?u:d) } + m[i]
(0 <= j < i)
0번째 시장의 위치를 s, 이득을 0으로 해줘서 시작점을 추가합시다.
마찬가지로 n+1번째 시장의 위치를 s, 이득을 0으로 해줘서 도착점을 추가합시다.
dp[n+1]을 구하면 답이 나오게 됩니다.
1 |
|
subtask 2. n≤300,000 / 같은 시간에 최대 1개의 시장 개최 (60점)
이 서브테스크를 푸는데 80분이 걸렸습니다.
O(n2)짜리 점화식을 O(n log n)까지 줄여야 합니다. Divide and Conquer Optimization(설명)을 생각해봤지만, 조건을 충족하지 못합니다.
일단 식을 분해해보았습니다.
- (l[i] > l[j])일 때
dp[i] = max{ dp[j] - ( l[i] - l[j] ) * D } + m[i]
dp[i] = max{ dp[j] + D*l[j] } - D*l[i] + m[i]
- (l[i] < l[j])일 때
dp[i] = max{ dp[j] - ( l[j] - l[i] ) * V } + m[i]
dp[i] = max{ dp[j] - U*l[j] } + U*l[i] + m[i]
i가 고정이 되어있다면, max 밖에 있는 것들은 상수취급할 수 있습니다. 그러면 max안에 있는, 즉 dp[j] + D*l[j]
나 dp[j] - U*l[j]
들의 최댓값만 O(log n)에 구할 수 있게 된다면 이 문제는 O(n log n)에 풀리게 될 것 입니다.
특정 구간 내에서 최댓값을 O(log n)만에 구할 수 있는 것은 Segment Tree 가 있습니다.
세그먼트 트리를 두 개 만들어서 하나는 dp[j] + D*l[j]
를 저장하고, 다른 한 곳에는 dp[j] - U*l[j]
를 저장하면 2번 섭테도 해결할 수 있습니다.
세그먼트 트리의 이름을 s1과 s2로 가정하면 아래와 같은 방법으로 구현할 수 있습니다.
dp[i] = max{ s1.query(0,l[j])-d*l[i], s2.query(l[j],500001)+u*l[i] } + m[i]
s1.update(l[i], dp[i]+d*l[i]); s2.update(l[i], dp[i]-u*l[i])
코드는 아래와 같습니다.
1 |
|
subtask 3. n≤300,000 / 같은 시간에 여러 개 시장 개최 가능 (100점)
이 서브테스크를 푸는데 250분이 걸렸습니다.
동시에 여러 개의 시장이 개최가 되면, 모두 갈 수는 있습니다.
(이 문제)와 마찬가지로 a와 b에서 동시에 시장이 개최되고 a와 b를 모두 방문한다면, a와 b 사이에 있는 시장은 모두 방문하는게 무조건 이득이라는 것을 알 수 있습니다. 그러므로 상인이 하루에 들린 시장들은 연속된 구간을 이룹니다.
구현을 하기에 앞서, 입력받은 데이터를 약간 다르게 저장을 해줍시다.
1 |
|
각 날짜별로 다른 배열에 저장해두고, 같은 날짜라면 시장의 위치 순으로 정렬을 해주었습니다.
각 날짜별로 처리를 할건데, 두 가지 배열을 선언하도록 하겠습니다.
dpl[j] = 상인이 해당 날짜에서 j번째 시장에 위치 / 상인은 j-1번째 시장에서 왔음
dpr[j] = 상인이 해당 날짜에서 j번째 시장에 위치 / 상인은 j+1번째 시장에서 왔음
dpl[j]와 dpr[j]는 각각 dpl[j-1]과 dpr[j+1]에서 식을 유도해낼 수 있습니다.
j-1번째 시장의 위치를 prv, j+1번째 시장의 위치를 nxt라 할 때, 조금 더 구체적인 방법은 아래와 같습니다. (pos : 시장의 위치, cost : 해당 시장의 이득)
- dpl[j]와 dpr[j]는
max{ s1.query(0, pos)-d*pos, s2.query(pos, 500002)+u*pos } + cost
- j-1 >= 0이라면
dpl[j] = max{ dpl[j], dpl[j-1] - D*(pos-prv) + cost }
- j+1 < size라면
dpr[j] = max{ dpr[j], dpr[j+1] - U*(nxt-pos) + cost }
- 해당 날짜에서 j번째 시장까지 방문할 때 최대 이득은
max{ dpl[j], dpr[j] }
전체 코드는 아래와 같습니다.
전체 코드
1 |
|