moonsoo5522   7년 전

N이 50인걸 보고 bitmask로는 힘들까 생각하다가, 그래도 한번 해보자는 생각으로 정적배열을 쓰지 않고 map을 이용해서 3차원 점화식을 만들어서 돌렸는데, 예제 테스트 케이스는 잘 통과하길래 한번 넣어봤는데 시간 초과가 뜨더라구요.

다른 분들은 혹시 어떤 방법으로 풀이하셨나요?

portableangel   7년 전

저는 일반적인 케이스에서 수식 전개를 통해 문제를 풀 순서를 정하는 방식으로 접근했습니다.

우선 가장 일반적인 케이스를 아래와 같이 정의합니다.

임의의 시점 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)

셋 중 맥스값을 리턴하게 하면 됩니다.

jseo   7년 전

이런 스케쥴링 관련된 문제에서는 항상 최적의 순서가 존재합니다.

즉, 

1) 최적의 순서대로 정렬

2) 그 순서를 유지하면서 최적의 답을 내는 부분 집합 구하기

2번은 N*T가 상대적으로 작기 떄문에 냅색 비슷하게 풀 수 있습니다.

moonsoo5522   7년 전

두분 답변 감사합니다. 다시 풀어보겠습니다~

rtbsha11   7년 전

portableangel, jseo 님 감사합니다.

댓글을 작성하려면 로그인해야 합니다.