9942번: 하노이의 네 탑

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	128 MB	789	223	167	32.617%

문제

하노이의 탑이라는 유명한 문제가 있다.

하지만 이 문제는 너무 유명한 나머지 이제는 식상하다.

그러니까 이번엔 탑을 3개가 아닌 4개로 늘려서 생각해보자!

N개의 원판과 4개의 막대가 있을 때, 즉 보조 막대가 한 개가 아닌 두 개이면 몇 번 움직여서 모든 원판을 끝의 원판으로 옮길 수 있을까?

4개의 막대를 이용해서 N개의 원판을 모두 옮기기 위한 최소 이동 횟수를 구해보자.

입력

각 줄에 원판의 개수 N(1 ≤ N ≤ 1000)이 주어진다.

출력

테스트 케이스와 함께 답을 출력한다(단, 답은 64-bit 정수 타입(e.g. long long)으로 표현 가능하다).

예제 입력 1

1
3
5

예제 출력 1

Case 1: 1
Case 2: 5
Case 3: 13

힌트

사실 막대가 4개 이상인 하노이의 탑 문제는 Open Problem이므로 이 답이 최적이라는 보장은 없다 :(

하지만, 2014년에 Frame–Stewart algorithm이 최적해를 준다는 것이 증명되었다.

W3sicHJvYmxlbV9pZCI6Ijk5NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NThcdWIxNzhcdWM3NzRcdWM3NTggXHViMTI0IFx1ZDBkMSIsImRlc2NyaXB0aW9uIjoiPHA+PGEgaHJlZj1cIlwvcHJvYmxlbVwvMTkxNFwiPlx1ZDU1OFx1YjE3OFx1Yzc3NFx1Yzc1OCBcdWQwZDE8XC9hPlx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWM3MjBcdWJhODVcdWQ1NWMgXHViYjM4XHVjODFjXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyOTQgXHViMTA4XHViYjM0IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAgXHVjNzc0XHVjODFjXHViMjk0IFx1YzJkZFx1YzBjMVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2VjXHViMmM4XHVhZTRjIFx1Yzc3NFx1YmM4OFx1YzVkNCBcdWQwZDFcdWM3NDQgM1x1YWMxY1x1YWMwMCBcdWM1NDRcdWIyY2MgNFx1YWMxY1x1Yjg1YyBcdWIyOThcdWI4MjRcdWMxMWMgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwITxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzZkMFx1ZDMxMFx1YWNmYyA0XHVhYzFjXHVjNzU4IFx1YjljOVx1YjMwMFx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWM5ODkgXHViY2Y0XHVjODcwIFx1YjljOVx1YjMwMFx1YWMwMCBcdWQ1NWMgXHVhYzFjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWI0NTAgXHVhYzFjXHVjNzc0XHViYTc0IFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNWVjXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWQzMTBcdWM3NDQgXHViMDVkXHVjNzU4IFx1YzZkMFx1ZDMxMFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzggXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+NFx1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjNmQwXHVkMzEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCZuYnNwO1x1YzYyZVx1YWUzMFx1YWUzMCBcdWM3MDRcdWQ1NWMmbmJzcDtcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5Jm5ic3A7XHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjNmQwXHVkMzEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEmbmJzcDsmbGU7Jm5ic3A7TiZuYnNwOyZsZTsmbmJzcDsxMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzY0MCBcdWQ1NjhcdWFlZDggXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNChcdWIyZTgsIFx1YjJmNVx1Yzc0MCA2NC1iaXQgXHVjODE1XHVjMjE4IFx1ZDBjMFx1Yzc4NShlLmcuIGxvbmcgbG9uZylcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNCkuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzBhY1x1YzJlNCZuYnNwOzxhIGhyZWY9XCJodHRwOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9Ub3dlcl9vZl9IYW5vaSNXaXRoX2ZvdXJfcGVnc19hbmRfYmV5b25kXCI+XHViOWM5XHViMzAwXHVhYzAwIDRcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc4Jm5ic3A7XHVkNTU4XHViMTc4XHVjNzc0XHVjNzU4IFx1ZDBkMSBcdWJiMzhcdWM4MWM8XC9hPlx1YjI5NCBPcGVuIFByb2JsZW1cdWM3NzRcdWJiYzBcdWI4NWMgXHVjNzc0IFx1YjJmNVx1Yzc3NCBcdWNkNWNcdWM4MDFcdWM3NzRcdWI3N2NcdWIyOTQgXHViY2Y0XHVjN2E1XHVjNzQwIFx1YzVjNlx1YjJlNCA6KDxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MsIDIwMTRcdWIxNDRcdWM1ZDAmbmJzcDtGcmFtZSZuZGFzaDtTdGV3YXJ0IGFsZ29yaXRobVx1Yzc3NCBcdWNkNWNcdWM4MDFcdWQ1NzRcdWI5N2MgXHVjOTAwXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM5OWRcdWJhODVcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5OTQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRm91ci1Ub3dlciBUb3dlcnMgb2YgSGFub2kiLCJkZXNjcmlwdGlvbiI6IjxwPlJlZmVyIHRvIHByb2JsZW0gdGhyZWUgZm9yIGEgZGVzY3JpcHRpb24gb2YgdGhlIGNsYXNzaWMgdGhyZWUtdG93ZXIgdmVyc2lvbiBvZiB0aGUgVG93ZXJzIG9mIEhhbm9pIHByb2JsZW0uPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHdlIGV4dGVuZCB0aGUgVG93ZXJzIG9mIEhhbm9pIHRvIGhhdmUgZm91ciB0b3dlcnMgYW5kIGFzayB0aGUgcXVlc3Rpb24gJmxkcXVvO1doYXQgYXJlIHRoZSBmZXdlc3QgbnVtYmVyIG9mIG1vdmVzIHRvIHNvbHZlIHRoZSBUb3dlcnMgb2YgSGFub2kgcHJvYmxlbSBmb3IgYSBnaXZlbiBuIGlmIHdlIGFsbG93IGZvdXIgdG93ZXJzIGluc3RlYWQgb2YgdGhlIHVzdWFsIHRocmVlPyZyZHF1bzsgV2Uga2VlcCB0aGUgcnVsZXMgb2YgdHJ5aW5nIHRvIG1vdmUgbiBkaXNrcyBmcm9tIG9uZSBzcGVjaWZpZWQgcG9zdCB0byBhbm90aGVyIGFuZCBkbyBub3QgYWxsb3cgYSBiaWdnZXIgZGlzayB0byBiZSBwdXQgb24gdG9wIG9mIGEgc21hbGxlciBvbmUuIFdoYXQgaXMgbmV3IGZvciB0aGlzIHByb2JsZW0gaXMgdG8gaGF2ZSB0d28gc3BhcmUgcG9zdHMgaW5zdGVhZCBvZiBqdXN0IG9uZS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRvIG1vdmUgMyBkaXNrcyBmcm9tIHBvc3QgQSB0byBwb3N0IEQsIHdlIGNhbiBtb3ZlIGRpc2sgMSBmcm9tIEEgdG8gQiwgZGlzayAyIGZyb20gQSB0byBDLCBkaXNrIDMgZnJvbSBBIHRvIEQsIGRpc2sgMiBmcm9tIEMgdG8gRCwgYW5kIGRpc2sgMSBmcm9tIEIgdG8gRCwgbWFraW5nIGEgdG90YWwgb2YgNSBtb3Zlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgYmUgcG9zaXRpdmUgaW50ZWdlcnMgKG4pLCBvbmUgcGVyIGxpbmUsIG5vbmUgYmVpbmcgbGFyZ2VyIHRoYW4gMSwwMDAuIEZvciBlYWNoIHZhbHVlIG9mIG4sIGNvbXB1dGUgdGhlIGZld2VzdCBudW1iZXIgb2YgbW92ZXMgZm9yIHRoZSBmb3VyLXRvd2VyIHByb2JsZW0uIFN0b3AgcHJvY2Vzc2luZyBhdCB0aGUgZW5kIG9mIHRoZSBmaWxlLiAoVGhlcmUgaXMgbm8gZW5kLW9mLWRhdGEgZmxhZy4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBmZXdlc3QgbnVtYmVyIG9mIG1vdmVzLiBGb2xsb3cgdGhpcyBmb3JtYXQgZXhhY3RseTogJmxkcXVvO0Nhc2UmcmRxdW87LCBvbmUgc3BhY2UsIHRoZSBjYXNlIG51bWJlciwgYSBjb2xvbiBhbmQgb25lIHNwYWNlLCBhbmQgdGhlIGFuc3dlciBmb3IgdGhhdCBjYXNlLiBZb3UgbWF5IGFzc3VtZSB0aGUgYW5zd2VyIHdpbGwgZml0IGluIGEgNjQtYml0IGludGVnZXIgdHlwZS4gRG8gbm90IHByaW50IGFueSB0cmFpbGluZyBzcGFjZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2013 D번

내용을 추가한 사람: jh05013
문제를 번역한 사람: WeissBlume

문제

문제

출처

ICPC

9942번 - 하노이의 네 탑 다국어

문제

입력

출력

제한

예제 입력 1

예제 출력 1

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

9942번 - 하노이의 네 탑 다국어

문제

입력

출력

제한

예제 입력 1 복사

예제 출력 1 복사

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

예제 입력 1

예제 출력 1