1일 1DP 2016.04.06 solution

1. 지우개 

https://www.acmicpc.net/problem/11881

Solution 1 :

dp[i][j] = A(a1) < A(a2) ... < A(aj) <= i 를 만족하는 모든 길이 j의 서로 다른 수열 a에 대해서, A(a1) * A(a2) ... * A(aj)의 합 이라고 정의합니다. 말이 어렵지만, 생각해보면 어려운 개념은 아닙니다.

cnt[i] = 부피 i의 지우개의 개수라고 정의합시다.

점화식은 다음과 같습니다 :

dp[i][0] = dp[i-1][0] + i * cnt[i]

dp[i][k] = dp[i-1][k-1] * i * cnt[i] + dp[i][k-1] (k < 0)

답은 dp[100000][2]입니다. 시간 복잡도는 O(n + max(ai)).

Solution 2 :

solution 1이 가장 쉬운 문제 치고는 살짝 어렵기에, 많은 분들이 solution 2로 풀지 않으셨을까 싶네요.

핵심적인 아이디어는 ai < aj < ak일때 aj의 값을 고정시키는 겁니다. (유용한 아이디어입니다) 모든 aj보다 작은 ai의 경우의 합. 모든 aj보다 큰 ai의 경우의 합이 필요하겠죠. 이는 각 지우개마다 O(n)에 가능합니다.

하지만, O(n^2) 는 좀 느립니다. 고로 부분합의 개념을 활용합시다. sum[i] = sum[i-1] + i * cnt[i]로 정의합니다. aj보다 작은 ai의 경우의 합은 sum[aj-1], 큰 경우의 합은 sum[100000] - sum[aj] 입니다. 시간 복잡도는 O(n + max(ai)).

2. 마라톤 2

https://www.acmicpc.net/problem/10653

편의상 K개의 체크포인트를 건너뛰었다 -> N - K개의 점을 지났다라고 정의하겠습니다. dp[i][j] = i번 점을 j번째로 지났다 라고 정의하면, 다음과 같은 점화식을 유도할 수 있습니다.

dp[i][j] = Min(dp[i-1][k] + |Xj - Xk| + |Yj - Yk|) for all 1 <= k < j (i >= 2)

시간 복잡도는 O(N^3).

3. 신기한 키보드

https://www.acmicpc.net/problem/1796

고정된 알파벳에 대해서 생각해보면 각각의 알파벳의 위치는 딱히 중요하지 않습니다. 'a'를 값으로 가지는 가장 왼쪽 / 오른쪽 만 찍고 오면 되니까요.

dp[i][j] = 'a' + i번째 알파벳까지 처리한 후 현재 j번째 포인트에 있다 라고 정의하면, dp[i][j] = Min(dp[i-1][k] + Cost(k, j, min_pos(i + 'a'), max_pos(i + 'a')) 입니다. 여기서 max_pos / min_pos는 각각의 알파벳 값을 가지는 최소 / 최대 위치입니다.

Cost(a, b, c, d)는, a -> b로 가야 하며, 왼쪽 c와, 오른쪽 d를 찍고 가야 할 때, 최소로 이동해야 하는 거리를 뜻합니다. 뭘 해야하는지 알고 있기 때문에 이 함수의 유도는 아주 쉽습니다. 고로 생략하겠습니다. 시간 복잡도는 O(alphabet * |S|^2).

4. 단조수열 만들기

https://www.acmicpc.net/problem/1209

편의상 B1≤B2≤…≤BN 를 만족하는 수열만 구하겠습니다. 반대는 입력을 뒤집으면 쉽게 해결 가능합니다.

핵심적인 관찰은, 입력으로 들어온 정수만으로도 정답 단조수열을 유도할 수 있다는 점입니다. 예를 들어, 입력으로 주어진 값이 1 / 3 / 1000000 이면, 4 ~ 999999에 있는 수들을 전혀 사용하지 않고도 최적의 단조 수열을 만들 수 있다는 뜻입니다. 증명은, 그 사이에 있는 수들을 인접한 입력값으로 이동시켜도 값의 변화가 없음을 보임으로써 가능합니다.

"좌표 압축"을 통해서 입력으로 주어진 값들의 범위를 줄입시다. 즉, 1 / 3 / 7 / 5 / 3이면 , 0 / 1 / 3 / 2 / 1와 같이 줄이는 것입니다. (외부 배열에, {1, 3, 5, 7} 이라는 값을 따로 저장해야 합니다) 처음 하면 당황스러울 수 있지만 C++의 unique / lower_bound 함수를 쓰면 어렵지 않게 가능합니다.

이제, DP[i][j] = i번째까지 수열을 만들었고, 현재 j번째 값일 때 주어진 값 최소화 라고 정의합시다. DP[i][j] = Min(DP[i][j-1], DP[i-1][j] + |Ai - Bj|) 입니다. 시간 복잡도는 O(N^2).

* 이 문제 NlgN 해법이 있습니다. 전 모르겠더라고요 ㅠㅠ 아이디어가 있으신 분들은 댓글로 적어주셨으면 합니다. 찾았습니다!

5. Matryoshka Dolls

https://www.acmicpc.net/problem/10462

만약에, 마트료시카 N개가 주어졌을 때, 이를 모두 중첩할 수 있는지 Yes / No으로 판별하는 문제를 푼다면, 어떻게 풀어야 할까요?

마트료시카를 크기 제한 순서대로 정렬한 후 단순히 끼워넣는, Greedy한 방식으로 체크할 수 있습니다. 저 방식으로 안 되면, 그 어떤 방식으로도 안됨을 증명할 수 있기 때문입니다. 애석하게도 이 방법만으로는 O(2^N * N)이기 때문에 문제를 해결할 수 없고, 여기에 DP를 섞어야 합니다. 크기 제한 순으로 정렬된 마트료시카 집합에서 DP를 돌립시다.

DP[i][j] = i번째까지의 마트료시카를 사용해서 j개를 쌓았을 때, 최소 무게 (불가능하면 inf) (W = 무게, L = 데드라인)

DP[i][j] = Min(DP[i-1][j], DP[i-1][j-1] + W[i]) 이며, DP[i][j] > L[i]일때 DP[i][j] = inf입니다. 시간 복잡도는 O(N^2).

직관적인 방법은 개수를 최대화하는 것인데, 왜 하필이면 무게를 최소화할까요? 간단히 말해서 만만한 놈을 팬다 (...) 라고 생각하시면 됩니다. 상태 공간은 (i, j, w) 와 같은 반환값이 없는 3차원 형태로 나타나며, j를 최대화하는 식으로, w를 최소화하는 식으로 모두 DP를 유도할 수 있습니다. 여기서는 j를 최대화하면 테이블을 잡을 수 없기 때문에 order를 맞춰주기 위해서 무조건 w를 최소화하는 식으로 DP를 유도해야 합니다. 전 이 문제에서 처음에 j를 최대화하는 식으로 점화식을 세웠다가 테이블이 너무 커져서 w를 최소화하는 쪽으로 바꿨습니다. 이렇게 상태를 자유자재로 변화시키는 것도 알아두면 유용한 방법입니다. (연습해볼만한 문제 : https://www.acmicpc.net/problem/10846. 쉽지는 않습니다.)

6. 상인

https://www.acmicpc.net/problem/5466

Step 1 : 모든 시장이 다른 날에 열린다고 하면, 쉽게 N^2 점화식을 유도할 수 있습니다. 시장을 모두 열리는 날짜 기준으로 정렬하고, DP[i] = i번 시장을 방문했을 때 최대 이익이라고 하면,

DP[i] = Max(DP[j] + (L[j] - L[i]) * D) (L[j] > L[i], j < i), Max(DP[j] + (L[i] - L[j]) * U) (L[j] <= L[i], j < i) + M[i]

0번 시장과 N+1번 시장을 S에서 열리는 0원짜리 시장으로 해석해두면 코딩이 편리하겠죠.

Step 2 : 모든 시장이 다른 날에 열릴 때, NlgN으로 시간을 줄여봅시다. 점화식을 풀어 쓰면

update DP[i] = Max(DP[j] + L[j] * D) - L[i] * D + M[i] (L[j] > L[i])

update DP[i] = Max(DP[j] - L[j] * U) + L[i] * U + M[i] (L[j] <= L[i])

같은 꼴이 나옵니다. 이제 이 점화식은 세그먼트 트리라는 자료 구조를 통해서 최적화할 수 있습니다. (자료 구조 설명은 생략합니다.) 세그먼트 트리는 구간의 최댓값과, 원소의 갱신을 O(lgN)에 할 수 있으므로, 크기 50만의 세그먼트 트리를 잡은 후

update DP[i] = SegmentTree1.Query(L[i] + 1, 500000) - L[i] * D + M[i]

update DP[i] = SegmentTree2.Query(0, L[i])+ L[i] * U + M[i]

SegmentTree1.update(L[i], DP[i] + L[i] * D)

SegmentTree2.update(L[i], DP[i] - L[i] * U)

.. 와 같은 요령으로 날짜가 다를 때는 O(NlgN)에 처리 가능합니다.

Step 3 : 같은 날에 시장이 열리는 것이 문제인데, 생각해 보면 같은 날에 상인이 상류에 있는 어떤 시장 / 하류에 있는 어떤 시장을 들렀다면, 그 과정에서 중간에 있는 시장을 모두 들렀음을 알 수 있습니다. 즉, 상인이 하루에 들린 시장은 연속된 구간을 이룹니다.

이를 통해서 DP를 조금 더 바꿔줄 수 있습니다. 각각의 날짜를 std::vector 같은 데 삽입하고, DPL[i][j]와 DPR[i][j]를 선언해서 문제를 해결합니다.

 * DPL[i][j] = i번째 날, j번째 시장에 있는 상인, 상인은 j-1번째 시장에서 내려왔거나 전날에서 이동했다.

 * DPR[i][j] = 반대.

DPL[i][j] / DPR[i][j]는 DPL[i][j-1], DPR[i][j+1]에서 관계식을 이끌어낼 수 있고, 아까의 세그먼트 트리에다가 이러한 관계식을 덧붙이면 같은 날에 들리는 시장을 처리할 수 있습니다.

 

7. sorting

쓸 수 있다면 나중에 쓸게요... 혹시 써주실 수 있는 분 있으시다면 감사하겠습니다 ㅠㅠ