시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB219895083945.499%

문제

아즈텍의 황제 쿠이틀라우악은 자신의 명예를 위해 피라미드를 만들려고 한다.

아즈텍 피라미드는 돌 블록을 이용해서 만든다. 블록은 1×1×1 크기의 정육면체이다. 쿠이틀라우악은 피라미드의 설립식 때, 블록 하나를 직접 땅에 놓았다. 그 다음 블록부터는 인부들이 설치하며, 이전에 놓여진 블록과 적어도 한 면 전체를 공유해야 한다.

왼쪽 두 개는 가능한 블록의 배치, 오른쪽 세 개는 불가능한 배치이다.

블록은 땅의 바로 위에 있거나, 블록의 아래에 있는 블록의 모든 면이 땅이나 다른 블록과 접할 때, 안정적이라고 한다. 피라미드의 모든 블록은 안정적이어야 한다.

아래 그림은 회색 블록을 놓았을 때이며, 그 블록이 안정적인 경우는 왼쪽 세 개, 아닌 경우는 오른쪽 두 개이다.

사용할 수 있는 블록의 개수가 주어졌을 때, 그 블록으로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사용할 수 있는 블록의 수 n이 주어진다. (1 ≤ n ≤ 109)

출력

첫째 줄에 블록 n개로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 출력한다.

예제 입력 1

6

예제 출력 1

2

예제 입력 2

5

예제 출력 2

1

예제 입력 3

20

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6Ijc3NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWM5ODhcdWQxNGQgXHVkNTNjXHViNzdjXHViYmY4XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDRcdWM5ODhcdWQxNGRcdWM3NTggXHVkNjY5XHVjODFjIFx1Y2ZlMFx1Yzc3NFx1ZDJjMFx1Yjc3Y1x1YzZiMFx1YzU0NVx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHViYTg1XHVjNjA4XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWQ1M2NcdWI3N2NcdWJiZjhcdWI0ZGNcdWI5N2MgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHVjOTg4XHVkMTRkIFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1YjI5NCBcdWIzY2MgXHViZTE0XHViODVkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YmUxNFx1Yjg1ZFx1Yzc0MCAxJnRpbWVzOzEmdGltZXM7MSBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVjNzc0XHViMmU0LiBcdWNmZTBcdWM3NzRcdWQyYzBcdWI3N2NcdWM2YjBcdWM1NDVcdWM3NDAgXHVkNTNjXHViNzdjXHViYmY4XHViNGRjXHVjNzU4IFx1YzEyNFx1YjliZFx1YzJkZCBcdWI1NGMsIFx1YmUxNFx1Yjg1ZCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjOWMxXHVjODExIFx1YjU0NVx1YzVkMCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHViZTE0XHViODVkXHViZDgwXHVkMTMwXHViMjk0IFx1Yzc3OFx1YmQ4MFx1YjRlNFx1Yzc3NCBcdWMxMjRcdWNlNThcdWQ1NThcdWJhNzAsIFx1Yzc3NFx1YzgwNFx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM5YzQgXHViZTE0XHViODVkXHVhY2ZjIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYTc0IFx1YzgwNFx1Y2NiNFx1Yjk3YyZuYnNwO1x1YWNmNVx1YzcyMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZCBcdWI0NTAgXHVhYzFjXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJlMTRcdWI4NWRcdWM3NTggXHViYzMwXHVjZTU4LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTM4IFx1YWMxY1x1YjI5NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzMwXHVjZTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3B5cmExLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc2cHg7IHdpZHRoOjUxM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmUxNFx1Yjg1ZFx1Yzc0MCBcdWI1NDVcdWM3NTggXHViYzE0XHViODVjIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWFjNzBcdWIwOTgsIFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViYTc0XHVjNzc0IFx1YjU0NVx1Yzc3NFx1YjA5OCBcdWIyZTRcdWI5NzggXHViZTE0XHViODVkXHVhY2ZjIFx1YzgxMVx1ZDU2MCBcdWI1NGMsIFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZTE0XHViODVkXHVjNzQwIFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVkNjhjXHVjMGM5IFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWIxOTNcdWM1NThcdWM3NDQgXHViNTRjXHVjNzc0XHViYTcwLCBcdWFkZjggXHViZTE0XHViODVkXHVjNzc0IFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNjdjXHVjYWJkIFx1YzEzOCBcdWFjMWMsIFx1YzU0NFx1YjJjYyBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjQ1MCBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHlyYTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTRweDsgd2lkdGg6NjM5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViZTE0XHViODVkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmUxNFx1Yjg1ZCBuXHVhYzFjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijc3NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBenRlYyBQeXJhbWlkIiwiZGVzY3JpcHRpb24iOiI8cD5BenRlYyBlbXBlcm9yIEN1aXRsJmFhY3V0ZTtodWFjIGlzIGdvaW5nIHRvIGJ1aWxkIGEgcHlyYW1pZCBpbiBoaXMgaG9ub3IuIFRoaXMgcHlyYW1pZCBzaG91bGQgYmUgdGFsbGVyIHRoYW4gcHJldmlvdXMgb25lcy48XC9wPlxyXG5cclxuPHA+VGhlIEF6dGVjIHB5cmFtaWQgaXMgYnVpbGQgb3V0IG9mIHN0b25lIGJsb2Nrcy4gRWFjaCBibG9jayBpcyAxJnRpbWVzOzEmdGltZXM7MS1odW5hYiBjdWJlLiBDdWl0bCZhYWN1dGU7aHVhYyBwbGFjZXMgXHVmYjAxcnN0IGJsb2NrIG9uIHRoZSBncm91bmQgZHVyaW5nIHRoZSBmb3VuZGF0aW9uIGNlcmVtb255LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgYmxvY2tzIG11c3Qgc2hhcmUgYSBmYWNlIHdpdGggYXQgbGVhc3Qgb25lIG9mIHRoZSBwcmV2aW91cyBibG9ja3MuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHlyYTMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA5cHg7IHdpZHRoOjUyNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBibG9jayBpcyBzdGFibGUgaWYgaXQgc3RhbmRzIG9uIHRoZSBncm91bmQsIG9yIGl0IHN0YW5kcyBvbiBhbm90aGVyIGJsb2NrLCB0aGF0IGhhcyBhIGJsb2NrIG9yIHRoZSBncm91bmQgbmV4dCB0byBlYWNoIGZhY2UuIFRvIHN0YW5kIHRoZSB0ZXN0IG9mIHRpbWUgdGhlIHB5cmFtaWQgbXVzdCBiZSBzdGFibGUgaS5lLiBlYWNoIGJsb2NrIG9mIGl0IG11c3QgYmUgc3RhYmxlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3B5cmE0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyN3B4OyB3aWR0aDo2NjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5DdWl0bCZhYWN1dGU7aHVhYyBhc2tzIHlvdSB0byBkZXRlcm1pbmUgdGhlIGhlaWdodCBvZiB0aGUgdGFsbGVzdCBzdGFibGUgcHlyYW1pZCB0aGF0IGNhbiBiZSBidWlsdCBvdXQgb2YgYXZhaWxhYmxlIGJsb2Nrcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBibG9ja3MsIGluY2x1ZGluZyB0aGUgXHVmYjAxcnN0IG9uZSAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgaGVpZ2h0IG9mIHRoZSB0YWxsZXN0IHN0YWJsZSBweXJhbWlkIHRoYXQgbWF5IGJlIGJ1aWx0IG91dCBvZiBuIGJsb2Nrcy4gVGhlIGhlaWdodCBtdXN0IGJlIG91dHB1dCBpbiBodW5hYnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Northern Eurasia > North-Western Russia Regional Contest > NEERC Northern Subregional 2012 A번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: doju