시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 69 9 9 60.000%

문제

x의 P승을(1 <= P <= 20,000) 최대한 빠르게 계산하고자 한다. 그런데 계산결과가 굉장히 크므로 여기서는 계산 도중 값을 저장하는 데 있어 두 개의 변수만을 사용한다.

두 변수 중 하나는 x로, 다른 하나는 1로 초기화되어 있다. 우리가 쓸 수 있는 연산은, 현재 저장되어 있는 값들을 서로 곱하거나 나누어서 그 결과값을 임의의 변수에 저장하는 것이다. 최종 결과가 저장되는 위치는 아무래도 좋다.

예를 들어 x^9을 계산하고자 할 때, 다음과 같은 방법이 가능하다.

연산 회수 0 1 2 3 4
변수1 x x x x^5 x^9 ☜☜☜
변수2 1 x^2 x^4 x^4 x^4

P를 입력받아, x^P를 구하기 위한 최소 연산 회수를 구하여라.

입력

첫째 줄에 P가 들어온다.

출력

최소 연산 회수를 출력한다.

예제 입력 1

31

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIwNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWI0ZWRcdWM4MWNcdWFjZjEgXHVhY2M0XHVjMGIwXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD54XHVjNzU4IFBcdWMyYjlcdWM3NDQoMSAmbHQ7PSBQICZsdDs9IDIwLDAwMCkgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhY2M0XHVjMGIwXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YWQ0OVx1YzdhNVx1ZDc4OCBcdWQwNmNcdWJiYzBcdWI4NWMgXHVjNWVjXHVhZTMwXHVjMTFjXHViMjk0IFx1YWNjNFx1YzBiMCBcdWIzYzRcdWM5MTEgXHVhYzEyXHVjNzQ0IFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVjNzg4XHVjNWI0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViY2MwXHVjMjE4XHViOWNjXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmNjMFx1YzIxOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViMjk0IHhcdWI4NWMsIFx1YjJlNFx1Yjk3OCBcdWQ1NThcdWIwOThcdWIyOTQgMVx1Yjg1YyBcdWNkMDhcdWFlMzBcdWQ2NTRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjNGY4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzQwLCBcdWQ2MDRcdWM3YWMgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjMTJcdWI0ZTRcdWM3NDQgXHVjMTFjXHViODVjIFx1YWNmMVx1ZDU1OFx1YWM3MFx1YjA5OCBcdWIwOThcdWIyMDRcdWM1YjRcdWMxMWMgXHVhZGY4IFx1YWNiMFx1YWNmY1x1YWMxMlx1Yzc0NCBcdWM3ODRcdWM3NThcdWM3NTggXHViY2MwXHVjMjE4XHVjNWQwIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Y2Q1Y1x1Yzg4NSBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjODAwXHVjN2E1XHViNDE4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWM1NDRcdWJiMzRcdWI3OThcdWIzYzQgXHVjODhiXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IHheOVx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTYwIFx1YjU0YywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NDglXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo2JVwiPlx1YzVmMFx1YzBiMCBcdWQ2OGNcdWMyMTg8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NiVcIj4wPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjYlXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo2JVwiPjI8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NiVcIj4zPFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjYlXCI+NDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cdWJjYzBcdWMyMTgxPFwvdGQ+XHJcblx0XHRcdDx0ZD54PFwvdGQ+XHJcblx0XHRcdDx0ZD54PFwvdGQ+XHJcblx0XHRcdDx0ZD54PFwvdGQ+XHJcblx0XHRcdDx0ZD54XjU8XC90ZD5cclxuXHRcdFx0PHRkPnheOSBcdTI2MWNcdTI2MWNcdTI2MWM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHViY2MwXHVjMjE4MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+eF4yPFwvdGQ+XHJcblx0XHRcdDx0ZD54XjQ8XC90ZD5cclxuXHRcdFx0PHRkPnheNDxcL3RkPlxyXG5cdFx0XHQ8dGQ+eF40PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5QXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU0NCwgeF5QXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzVmMFx1YzBiMCBcdWQ2OGNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBQXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkNWNcdWMxOGMgXHVjNWYwXHVjMGIwIFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjA3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvd2VyIEh1bmdyeSBDb3dzIiwiZGVzY3JpcHRpb24iOiI8cD5GSiYjMzk7cyBjb3dzIHdvdWxkIGxpa2UgdG8gYmUgYWJsZSB0byBjb21wdXRlIGludGVnZXIgcG93ZXJzIFAgKDEgJmx0Oz0gUCAmbHQ7PSAyMCwwMDApIG9mIG51bWJlcnMgdmVyeSBxdWlja2x5LCBidXQgbmVlZCB5b3VyIGhlbHAuIEJlY2F1c2UgdGhleSYjMzk7cmUgZ29pbmcgdG8gYmUgY29tcHV0aW5nIHBvd2VycyBvZiB2ZXJ5IGxhcmdlIG51bWJlcnMsIHRoZXkgY2FuIG9ubHkga2VlcCBhcm91bmQgdHdvIHdvcmsgdmFyaWFibGVzIGZvciBpbnRlcm1lZGlhdGUgcmVzdWx0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IG9mIHRob3NlIHdvcmsgdmFyaWFibGVzIGlzIGluaXRpYWxpemVkIHRvIHRoZSBudW1iZXIgKGRlbm90ZWQgeCkgZm9yIHdoaWNoIHRoZXkgYXJlIGNhbGN1bGF0aW5nIHRoZSBwb3dlcjsgdGhlIG90aGVyIGlzIGluaXRpYWxpemVkIHRvIDEuIFRoZSBjb3dzIGNhbiBib3RoIG11bHRpcGx5IGFuZCBkaXZpZGUgYW55IHBhaXIgb2YgdGhlIHdvcmsgdmFyaWFibGVzIGFuZCBzdG9yZSB0aGUgcmVzdWx0IGluIGFueSB3b3JrIHZhcmlhYmxlLCBidXQgYWxsIHJlc3VsdHMgYXJlIHN0b3JlZCBhcyBpbnRlZ2Vycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHRoZXkgd2FudCB0byBjb21wdXRlIHheMzEsIG9uZSB3YXkgdG8gcGVyZm9ybSB0aGUgY2FsY3VsYXRpb24gaXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBXVjEgIFdWMlxyXG5cclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBTdGFydDogICB4ICAgIDFcclxuXHJcbiAgIE11bHRpcGx5IGZpcnN0IGJ5IGZpcnN0LCBzdG9yZSBpbiBzZWNvbmQ6ICAgeCAgIHheMlxyXG5cclxuICAgICAgICAgICAgICAgICAgTXVsdGlwbHkgc2Vjb25kIGJ5IHNlY29uZDogICB4ICAgeF40XHJcblxyXG4gICAgICAgICAgICAgICAgICBNdWx0aXBseSBzZWNvbmQgYnkgc2Vjb25kOiAgIHggICB4XjhcclxuXHJcbiAgICAgICAgICAgICAgICAgIE11bHRpcGx5IHNlY29uZCBieSBzZWNvbmQ6ICAgeCAgIHheMTZcclxuXHJcbiAgICAgICAgICAgICAgICAgIE11bHRpcGx5IHNlY29uZCBieSBzZWNvbmQ6ICAgeCAgIHheMzJcclxuXHJcbiAgICAgICAgICAgICAgICAgICAgIERpdmlkZSBzZWNvbmQgYnkgZmlyc3Q6ICAgeCAgIHheMzFcclxuPFwvcHJlPlxyXG5cclxuPHA+VGh1cywgeF4zMSBjYW4gY29tcHV0ZWQgaW4gc2l4IG9wZXJhdGlvbnMuIEdpdmVuIHRoZSBwb3dlciB0byBiZSBjb21wdXRlZCBhbmQgdGhlIHRoZSBudW1iZXIgb2Ygd29yayB2YXJpYWJsZXMsIGZpbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgdG8gY2FsY3VsYXRlIHRoZSBwb3dlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBvbmUgaW50ZWdlcjogUC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIGl0IHJlcXVpcmVzIHRvIGNvbXB1dGUgdGhlIHBvd2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

  • 데이터를 추가한 사람: doju
  • 문제의 오타를 찾은 사람: kcm1700