시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 512 MB 180 126 98 67.586%

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

예제 입력 1

25

예제 출력 1

1

예제 입력 2

26

예제 출력 2

2

예제 입력 3

11339

예제 출력 3

3

예제 입력 4

34567

예제 출력 4

4
W3sicHJvYmxlbV9pZCI6IjE3NjI2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiRm91ciBTcXVhcmVzIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI3N2NcdWFkZjhcdWI3OTFcdWM4ZmNcdWIyOTQgMTc3MFx1YjE0NFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVjNzkwXHVjNWYwXHVjMjE4XHViMjk0IFx1YjEzNyBcdWQ2MzlcdWM3NDAgXHVhZGY4IFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1Yzk5ZFx1YmE4NVx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjI5NCBcdWJjZjVcdWMyMThcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgMjZcdWM3NDAgNTxzdXA+MjxcL3N1cD5cdWFjZmMgMTxzdXA+MjxcL3N1cD5cdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0OyBcdWI2MTBcdWQ1NWMgNDxzdXA+MjxcL3N1cD4gKyAzPHN1cD4yPFwvc3VwPiZuYnNwOysgMTxzdXA+MjxcL3N1cD5cdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzVlZFx1YzBhY1x1YzgwMVx1YzczY1x1Yjg1YyBcdWM1NTRcdWMwYjBcdWM3NTggXHViYTg1XHVjMjE4XHViNGU0XHVjNWQwXHVhYzhjIFx1YWNmNVx1ZDFiNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYjM4XHVjODFjXHVhYzAwIFx1YmMxNFx1Yjg1YyBcdWM3OTBcdWM1ZjBcdWMyMThcdWI5N2MgXHViMTM3IFx1ZDYzOVx1Yzc0MCBcdWFkZjggXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxY1x1YWNmMVx1YzIxOCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YzVjOFx1YjJlNC4gMTkwMFx1YjE0NFx1YjMwMCBcdWNkMDhcdWJjMThcdWM1ZDAgXHVkNTVjIFx1YzU1NFx1YzBiMFx1YWMwMFx1YWMwMCAxNTY2MyA9IDEyNTxzdXA+MjxcL3N1cD4mbmJzcDsrIDY8c3VwPjI8XC9zdXA+ICsgMTxzdXA+MjxcL3N1cD4gKyAxPHN1cD4yPFwvc3VwPlx1Yjc3Y1x1YjI5NCBcdWQ1NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0XHViMzcwIDhcdWNkMDhcdWFjMDAgXHVhYzc4XHViODM4XHViMmU0XHViMjk0IFx1YmNmNFx1YWNlMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzg4MCBcdWIzNTQgXHVjNWI0XHViODI0XHVjNmI0IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgNTZcdWNkMDhcdWFjMDAgXHVhYzc4XHViODM4XHViMmU0OiAxMTMzOSA9IDEwNTxzdXA+MjxcL3N1cD4gKyAxNTxzdXA+MjxcL3N1cD4gKyA4PHN1cD4yPFwvc3VwPiArIDU8c3VwPjI8XC9zdXA+LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMTggPGVtPm48XC9lbT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgPGVtPm48XC9lbT5cdWM3NDQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWMyMTggXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IDxlbT5uPFwvZW0+XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjLCAxICZsZTsgPGVtPm48XC9lbT4gJmxlOyA1MCwwMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDU2OVx1Yzc3NCA8ZW0+bjxcL2VtPlx1YWNmYyBcdWFjMTlcdWFjOGMgXHViNDE4XHViMjk0IFx1YzgxY1x1YWNmMVx1YzIxOFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3NjI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRm91ciBTcXVhcmVzIiwiZGVzY3JpcHRpb24iOiI8cD5JdCB3YXMgcHJvdmVuIGJ5IExhZ3JhbmdlIGluIDE3NzAgdGhhdCBldmVyeSBuYXR1cmFsIG51bWJlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgdGhlIHN1bSBvZiBmb3VyIG9yIGZld2VyIHNxdWFyZXMuIFNvbWUgbnVtYmVycyBhcmUgcmVwcmVzZW50ZWQgaW4gbXVsdGlwbGUgd2F5cy4gRm9yIGV4YW1wbGUsIDI2IGlzIHRoZSBzdW0gb2YgNTxzdXA+MjxcL3N1cD4mbmJzcDthbmQgMTxzdXA+MjxcL3N1cD47IGl0IGNhbiBhbHNvIGJlIHJlcHJlc2VudGVkIGFzIDQ8c3VwPjI8XC9zdXA+ICsgMzxzdXA+MjxcL3N1cD4gKyAxPHN1cD4yPFwvc3VwPi4gRXhwcmVzc2luZyBhIG51bWJlciBhcyB0aGUgc3VtIG9mIGZvdXIgb3IgZmV3ZXIgc3F1YXJlcyBpcyBoaXN0b3JpY2FsbHkgYSBjb21tb24gcHJvYmxlbSBwb3NlZCB0byBsaWdodG5pbmcgY2FsY3VsYXRvcnMuIEl0IHdhcyByZXBvcnRlZCBpbiB0aGUgZWFybHkgMTkwMHMgdGhhdCBhIGNhbGN1bGF0b3IgcHJvZHVjZWQgYSBzb2x1dGlvbiBvZiAxNTY2MyA9IDEyNTxzdXA+MjxcL3N1cD4gKyA2PHN1cD4yPFwvc3VwPiArIDE8c3VwPjI8XC9zdXA+ICsgMTxzdXA+MjxcL3N1cD4gaW4gOCBzZWNvbmRzLiBBIG1vcmUgZGlmZmljdWx0IHByb2JsZW0gdG9vayA1NiBzZWNvbmRzOiAxMTMzOSA9IDEwNTxzdXA+MjxcL3N1cD4gKyAxNTxzdXA+MjxcL3N1cD4gKyA4PHN1cD4yPFwvc3VwPiZuYnNwOysgNTxzdXA+MjxcL3N1cD4uPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbmF0dXJhbCBudW1iZXIgPGVtPm48XC9lbT4sIHdyaXRlIGEgcHJvZ3JhbSB0byBleHByZXNzIDxlbT5uPFwvZW0+IGFzIHRoZSBzdW0gb2YgYXMgZmV3IHNxdWFyZXMgYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgbmF0dXJhbCBudW1iZXIgPGVtPm48XC9lbT4sIHdoZXJlIDEgJmxlOyA8ZW0+bjxcL2VtPiAmbGU7IDUwLDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIHdoaWNoIGNvbnRhaW5zIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzcXVhcmVzIHdob3NlIHN1bSBpcyBlcXVhbCB0byA8ZW0+bjxcL2VtPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=