cjswo8219   11달 전

문제에서 만약 2의 거듭제곱을 만들 수 없는 경우 -1을 출력한다와 같은 문장이 없기 때문에

모든 수는 2의 거듭제곱을 만들 수 있다고 가정했습니다.

그리고 그리디하게 큰 수부터 2의 거듭제곱을 매칭해나갔고, 매칭이 되면 break를 걸었기 때문에 한 번만 매칭되는 걸 보장했고,

납도 for문으로 돌았기 때문에 1~N까지 순서대로 출력하는 것도 보장했습니다.


근데 0%에서 바로 틀리는데 뭐가 문제인지 모르겠습니다..


완성된 출력을 단순하게 뒤집을 때 (reverse), 두 자릿수 이상인 경우 문제가 발생합니다.

알고리즘은 맞는 것으로 보입니다.

cjswo8219   11달 전

답변 감사합니다! 추가질문이 있습니다!

제가 처음에는 아래와 같이 1부터 N까지 오름차순으로 체크를 했었습니다. 이때는 출력을 뒤집을 필요가 없었는데도 오답처리가 되었습니다.


여러 풀이 블로그를 찾아보면서 i = 1부터 경우의수를 찾으면 너무 많으니 내림차순으로 해서 찾는게 빠르다고 해서 변경하긴 했는데

사실 아래와 같은 풀이에서는 경우의 수를 찾으면 바로 break가 되기 때문에 딱히 시간이 오래걸리지 않을 것 같다고 생각합니다.(내림차순이랑 비슷할 것이라고 생각됩니다.)

왜 틀린지 이유가 궁금합니다..

doju   11달 전

3을 입력해 보세요.

말장난처럼 보일 수도 있지만, 처음에 가정하신 대로 언제나 답을 만들 수 있는 이유는 작성하신 풀이대로 내림차순으로 그리디하게 매칭하면 항상 답이 만들어지기 때문입니다. 왜 이 전략이 실패하지 않는지 확실히 이해하시면 두 번째 질문에도 수월하게 답을 내리실 수 있을 겁니다.
힌트를 드리면 귀납법을 접목시켜 생각해 보세요.

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