dltkdgkr123   1년 전

해당 문제는 TC 범위가 적혀있지 않습니다.

문제를 풀다보면, 마찬가지인 문제를 간간히 발견할 수 있습니다.

그냥 누락됐거나 귀찮은건가요? 

아니면, 유의미한 이유나 암묵적인 PS의 약속이 있는건가요? 충분히 최적화해라 히히 라는 느낌으로요

redcube231   1년 전

저는 보통은 한 TC의 가장 최적화된 풀이에서 감당 가능한 크기의 T가 주어진다고 가정하고 풀고, 출제자들도 말이 되게 문제를 만들어야 해서 빅O의 총 연산이 1억회를 초과한다든지 그렇게 내지는 않습니다.

암묵적으로 가장 최악의 경우를 가정하고 푸는 것 같습니다.

wizardrabbit   1년 전

옛날에 출제된 문제들의 경우 테스트 케이스의 개수 자체는 주어지지 않는 특징들이 있는 것 같습니다. 이 경우 대부분의 상황이라면 테스트 케이스의 수 자체가 풀이에 큰 영향을 줄 정도로 많지 않은 경우가 많습니다. 예를 들면 $50$개, $100$개 정도라든지요. 물론 그렇지 않은 경우도 있어 골치 아플 때도 있습니다.

요즘 출제되는 문제들은 테스트 케이스가 여러 개일 경우 항상 개수를 명시합니다. 즉, 테스트 케이스의 개수 또한 문제에서 반드시 명시해야 하는 정보입니다. 이렇게 옛날에 출제된 문제라면 어쩔 수 없지만 새롭게 올라오는 문제에서 테스트 케이스의 개수가 명시되어 있지 않다면 대부분 문제 조건 누락이므로 오타/오역/요청 게시판에 적어보시는 것도 좋은 방법일 것 같습니다(이 문제는 말고요).

dltkdgkr123   1년 전

사실 이 문제가 50개 100개가 아닌 그 부류인 것 같아서 궁금했습니다.

두 분 답변 감사드립니다 잘 읽었습니다.

wizardrabbit   1년 전

꽤 많은 편이네요, 확인해 보니까 테스트 케이스의 개수는 최악 $2\,000$개입니다. 매 테스트 케이스마다 $dp$배열을 매번 새로 만든다면 시간 초과를 받기 쉽겠군요.

최초 $1$회만 $dp$배열을 만든 후 입력이 들어올 때마다 미리 구해놓은 값을 바로바로 출력하는 방법으로 접근해야 풀 수 있겠네요.

dltkdgkr123   1년 전

말씀하신 방법을 썼고, 50개 정도겠거니 하면서 내서 시간초과를 받았습니다.

이후 gpt로 몇 개 정도면 터지는지 대략 물어봐서 2~3천개라고 유추했습니다.

어썰션 노가다까지 감사드립니다. 생각했던 내용이랑 너무 똑같아서 제 코드라도 보신 줄 알았네요.

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