gomino   1년 전

N 개의 막대를 가지고서 가장 큰 넓이를 가지는 직사각형을 구하는 문제인데,

N = 16 이라서 중복된 경우를 제거하고 완전탐색을 돌렸는데 시간초과가 나네요...

각 막대당 길이가 1이상 10이하여서 중복된 경우가 반드시 나오기 마련이고 따라서 완전탐색을 중복되지 않게 돌리면 될것이라 생각했습니다.

시간초과가 나서 메모이제이션을 할 수 없을까 생각해봐도 딱히 좋은 수가 떠오르지가 않네요...

어떤 식으로 접근해야 할까요?

Nada   1년 전

저도 시간초과였는데 완전 말도 안되는 경우를 가지치기 하니까 답이 나오네요

1. w*h > 여태까지 구한 답

2. w <= h 일 때 2*w + 2*h <= 막대기 전체 길이

3. w <= h 일 때 4*w <= 막대기의 전체길이

등과 같은 조건을 추가하니까 무리없이 나오네요.

gomino   1년 전

Nada

도움주신덕분에 해결하였습니다!!!! 정말 감사드립니다^^

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