khy0419   2년 전

조합으로 푸는걸 연습한다고 한번 해봤습니다.

아래의 방법에 따라 코드를 작성했으며, 현재 50%까지 가고 틀렸습니다가 발생합니다.

반례가 있다면 알려주시면 감사하겠습니다.

테스트 케이스 및 
1

5000000 
5000000
5000000 
는 정상적으로 나옵니다.

evenharder   2년 전

1 << K는 int형이기 때문에 K가 32만 넘어가도 값이 0이 되어버립니다. long long int로 해도 K가 64만 넘어가면 0이 되어버리고요.

이 점을 고려하지 않고도 K가 10^6까지 갈 수 있다는 걸 생각하면 이 풀이방법은 시간복잡도 O(2^K)가 되기 때문에 너무 느립니다.

모든 조합을 고려하는 풀이를 짜고 싶으시다면 이중 반복문으로 시간복잡도 O(K^2)의 방법을 생각해볼 수 있지만 이 역시 느린 걸 알고 계실 것 같습니다. 꼭 모든 수의 쌍을 고려해야 풀 수 있는 것은 아니므로 이를 고려하여 보다 효율적인 접근을 해보시기 바랍니다.

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