2205번 - 저울 추 만들기
문제에서 만약 2의 거듭제곱을 만들 수 없는 경우 -1을 출력한다와 같은 문장이 없기 때문에
모든 수는 2의 거듭제곱을 만들 수 있다고 가정했습니다.
그리고 그리디하게 큰 수부터 2의 거듭제곱을 매칭해나갔고, 매칭이 되면 break를 걸었기 때문에 한 번만 매칭되는 걸 보장했고,
납도 for문으로 돌았기 때문에 1~N까지 순서대로 출력하는 것도 보장했습니다.
근데 0%에서 바로 틀리는데 뭐가 문제인지 모르겠습니다..
완성된 출력을 단순하게 뒤집을 때 (reverse), 두 자릿수 이상인 경우 문제가 발생합니다.
알고리즘은 맞는 것으로 보입니다.
답변 감사합니다! 추가질문이 있습니다!
제가 처음에는 아래와 같이 1부터 N까지 오름차순으로 체크를 했었습니다. 이때는 출력을 뒤집을 필요가 없었는데도 오답처리가 되었습니다.
여러 풀이 블로그를 찾아보면서 i = 1부터 경우의수를 찾으면 너무 많으니 내림차순으로 해서 찾는게 빠르다고 해서 변경하긴 했는데
사실 아래와 같은 풀이에서는 경우의 수를 찾으면 바로 break가 되기 때문에 딱히 시간이 오래걸리지 않을 것 같다고 생각합니다.(내림차순이랑 비슷할 것이라고 생각됩니다.)
왜 틀린지 이유가 궁금합니다..
3을 입력해 보세요.
3
말장난처럼 보일 수도 있지만, 처음에 가정하신 대로 언제나 답을 만들 수 있는 이유는 작성하신 풀이대로 내림차순으로 그리디하게 매칭하면 항상 답이 만들어지기 때문입니다. 왜 이 전략이 실패하지 않는지 확실히 이해하시면 두 번째 질문에도 수월하게 답을 내리실 수 있을 겁니다.힌트를 드리면 귀납법을 접목시켜 생각해 보세요.
댓글을 작성하려면 로그인해야 합니다.
cjswo8219 11달 전
문제에서 만약 2의 거듭제곱을 만들 수 없는 경우 -1을 출력한다와 같은 문장이 없기 때문에
모든 수는 2의 거듭제곱을 만들 수 있다고 가정했습니다.
그리고 그리디하게 큰 수부터 2의 거듭제곱을 매칭해나갔고, 매칭이 되면 break를 걸었기 때문에 한 번만 매칭되는 걸 보장했고,
납도 for문으로 돌았기 때문에 1~N까지 순서대로 출력하는 것도 보장했습니다.
근데 0%에서 바로 틀리는데 뭐가 문제인지 모르겠습니다..