djm03178   4년 전

이 FAQ는 효율성에 상관 없이 이 문제를 푸는 것이 목적인 분들을 위해 작성되었습니다.

  1. 이 문제는 모든 경우의 수를 정직하게 따져보는 것이 의도인 문제입니다. 수행 시간을 줄이기 위한 묘기는 따로 필요하지 않습니다. 물론 실제로 시간 복잡도를 개선하는 것이 불가능한 것은 아니나, 문제의 제한인 N <= 100은 모든 가능한 세 카드의 조합을 1초 내에 뽑아보는 데에 전혀 무리가 없는 제한이기 때문에 전부 해보아도 되고, 반면에 증명할 수 없는 방법으로 탐색을 중도에 종료하도록 하는 것은 매우 위험합니다.
  2. 예를 들어, 굳이 카드를 정렬할 필요가 없습니다. 어차피 모든 경우의 수를 따져볼 것이기 때문입니다.
  3. 루프 중간에 break를 할 필요도 없습니다. 그것 때문에 따져보지 못하는 경우가 생깁니다.
  4. 세 카드를 뽑는 로직을 다르게 할 필요도 없습니다. 예를 들어, 첫 두 장을 먼저 연속된 카드로 뽑아놓고 나머지 한 장을 루프를 돌려 찾는 방식으로 하면 틀립니다. 첫 두 장이 연속되지 않게 하는 것이 최적일 수도 있습니다. 세 장을 모두 같은 방법으로 뽑으세요.
  5. 답 갱신은 세 장을 뽑았을 때마다 하면 됩니다. 굳이 분기를 나눠서 어떨 땐 갱신을 미루고, 다른 변수에 저장해보는 등 할 필요가 없습니다. "M을 넘지 않으면서 지금까지 찾았던 최댓값보다 크다면, 답을 갱신한다"를 모든 경우에 대해 똑같이 수행하면 됩니다.

요약하자면, 문제를 쉽고 단순하게 풀자는 것입니다. 어려운 기법이 동원될 필요가 없다면, 굳이 쓸 필요가 없습니다. 특히 그 방법이 최적이라는 것을 증명할 수 없다면, 아예 사용해서는 안 됩니다.

ryan2020   3년 전

꿀팁 감사합ㄴ디ㅏ

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