mrseos   3년 전

안녕하세요?

스타트와 링크 문제를 풀면서 궁금한 점이 생겨 질문드립니다.

저는 조합을 이용하여 문제를 풀었고,

스타트 팀이 N/2 번째를 뽑는 순간 최소를 출력하고 종료를 시켰습니다.

이유는 스타트팀이 0번째 뽑는 순간에 이미 링크팀이 자연스럽게 N/2 를 가져간다 생각했기 때문에

최소가 되는 값을 구할 땐 모두 검사할 필요가 없다고 생각들었기 때문입니다.

http://boj.kr/73d99e73e1c5441e...

위 코드는 N/2일 때 종료한 코드입니다.

그런데 오히려 아래의 코드(모든 조합을 다 계산하여 구한 경우)보다 시간과 메모리를 더 잡아먹는 것을 확인했습니다.

http://boj.kr/270e279b2217442a...

그다지 크게 차이는 안나지만 제 생각에는 오히려 메모리와 수행시간이 더 줄어야 할 것 같은데

더 잡아먹는 부분이 잘 이해되지않아서 질문드리게 됐습니다.

읽어주셔서 감사합니다.

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