저는 일반적인 케이스에서 수식 전개를 통해 문제를 풀 순서를 정하는 방식으로 접근했습니다.
우선 가장 일반적인 케이스를 아래와 같이 정의합니다.
임의의 시점 T에 남은 문제들이 여러 개 있습니다. 이 때, 지금 시점에 풀 첫 문제를 i, 두 번째 문제를 j라고 합시다.
i -> j 순서로 풀게 되면 얻는 점수는 (Mi - T*Pi) + (Mj - (T+Ri)*Pj) 가 됩니다.
j -> i 순서로 풀게 되면 얻는 점수는 (Mj - T*pj) + (Mi - (T+Rj)*Pi) 가 됩니다.
두 식을 전개해보면, Mi - T*Pi + Mj - T*Pj - Ri*Pj, Mj - T*pj + Mi - T*Pi - Pi*Rj 가 됩니다. 이 두 식을 각각 식 1, 식 2라고 합시다.
만일 식 1 > 식 2라면 i->j 순서로 푸는 것이 이득이고, 식 1 < 식 2라면 j->i 순서로 푸는 것이 이득입니다.
부등식을 푸는 데 동일한 항은 필요가 없으므로 식 1과 2에서 동일한 항을 모두 소거한 뒤 정리하면
식 1은 -Ri*Pj, 식 2는 -Pi*Rj가 됩니다.
즉 -Ri*Pj > -Pi*Rj 인 경우에 i->j 순서로 푸는 것이 이득입니다.
다시 한번 정리해보면, Ri/Pi < Rj/Pj 일 경우 i->j 순서로 푸는 것이 이득입니다. 여기까지 전개하면, 두 식이 서로 독립적이라는 것을 드디어 확인할 수가 있습니다.
네. 사실 R, P 값만으로 각 문제의 우선순위를 다른 문제와는 상관없이 구할 수가 있었네요.
그렇다면 두 개의 문제의 우선순위를 비교해 계속해서 스왑 소팅이 가능하므로, 결국 두 인접한 문제뿐 아니라 모든 문제 쌍에 대해
우선순위를 기반으로 풀 순서를 정해버릴 수가 있습니다.
풀 문제의 부분집합을 골랐다면, 해당 문제들을 푸는 순서는 하나로 확정된다는 의미입니다.
따라서, 우선 문제를 Ri/Pi의 순으로 정렬해 둡니다. 우리는 이 순서대로만 풀어야 합니다.
이제 dp가 참조할 내용은
1. 현재 번호의 문제를 풀고 다음 번호의 문제를 본다.
2. 현재 번호의 문제를 버리고 다음 번호의 문제를 본다. 현재 번호의 문제는 영영 풀 일이 없다. (뒤 문제를 풀고 다시 이걸 풀면 순서가 역전되므로)
3. 아무 것도 안 한다. (return 0)
셋 중 맥스값을 리턴하게 하면 됩니다.
moonsoo5522 7년 전
N이 50인걸 보고 bitmask로는 힘들까 생각하다가, 그래도 한번 해보자는 생각으로 정적배열을 쓰지 않고 map을 이용해서 3차원 점화식을 만들어서 돌렸는데, 예제 테스트 케이스는 잘 통과하길래 한번 넣어봤는데 시간 초과가 뜨더라구요.
다른 분들은 혹시 어떤 방법으로 풀이하셨나요?