silas   8년 전

D번 문제가 제한시간 초과로 안 풀렸네요.


혹시 푸신 분 있으시면 어떻게 푸신 건지 궁금합니다.


문제를 올려서 공유하고 싶은데 유출을 말아달라고 주최측에서 부탁했다고 하더라고요.

august14   8년 전

http://judge.lavida.us/problemset.php?page=21

D는 전형적인 DP문제입니다.

silas   8년 전

감사합니다.

DP로 풀어보려 했는데 시간 복잡도가 N * M * 10 정도 나오더군요.

각 악기마다 연주자의 수가 0~10명일 때를 각각 계산하다보니 그렇게 되는데, 혹시 이보다 나은 방법이 있나요?

괜찮다면 코드도 올려보겠습니다.

august14   8년 전

맞는 풀이인 것 같은데요?

silas   8년 전

그런가요? lavida에서 돌려봐도 시간초과라고 나오는 걸로 봐서 잘못 구현된 부분이 있을 것 같아서요. 아래와 같이 풀었습니다.

http://ideone.com/Klg6WZ

silas   8년 전

아.. 실수한 부분을 찾았네요. 감사합니다.

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