문제
기존 하노이는 모든 학생이 알 것이라 판단하여 설명을 생략한다.
우리는 하노이의 이동을 알파벳 두 글자로 표현할 수 있는데, 예를 들어 A번 폴에서 B번 폴로 가장 위에 있는 디스크를 옮기는 것을 AB라고 표현한다고 한다. 변형 하노이는 문제 조건에 만족하도록 옮기는 것이다. 즉, 자기 임의적으로 디스크를 옮길 수 없다. 디스크를 옮기는 조건은 아래와 같다.
․ 동일한 디스크를 연속으로 두 번 옮길 수 없다.
․ 총 옮길 수 있는 경우는 6가지(AB, AC, BA, BC, CA, CB)이고 이 여섯 가지의 옮기는 경우의 우선순위가 주어진다. 즉, 1번 조건을 만족하는 옮길 수 있는 경우가 두 가지 이상 존재하면 그 중 우선순위가 높은 것을 택해야 한다.
문제는 위 조건에 따라 판을 옮길 때 모든 디스크를 B폴이나 C폴 중 한 폴로 모두 옮겼을 때 횟수가 몇 번인지 구하는 것이다. (위 조건을 만족하도록 옮기다 보면 항상 어느 폴로 모두 옮겨진다고 한다.)
출력
첫 줄에 이동횟수를 출력한다. 답은 10^18보다 작다고 가정한다.
힌트
1. 1번 디스크를 A->B로 옮긴다.
2. 2번 디스크를 A->C로 옮긴다.
3. 1번 디스크를 B->A로 옮긴다.
4. 2번 디스크를 C->B로 옮긴다.
5. 1번 디스크를 A->B로 옮기면 끝나게 된다.
W3sicHJvYmxlbV9pZCI6IjExNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYzBcdWQ2MTUgXHVkNTU4XHViMTc4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIHdpZHRoPVwiMjc4XCIgaGVpZ2h0PVwiODhcIiBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvMjAxMDAzXC9oYWhhaC5qcGdcIiBcLz48XC9wPlxyXG48cD5cdWFlMzBcdWM4NzQgXHVkNTU4XHViMTc4XHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNTRjIFx1YWM4M1x1Yzc3NFx1Yjc3YyBcdWQzMTBcdWIyZThcdWQ1NThcdWM1ZWMgXHVjMTI0XHViYTg1XHVjNzQ0IFx1YzBkZFx1YjdiNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cdWM2YjBcdWI5YWNcdWIyOTQgXHVkNTU4XHViMTc4XHVjNzc0XHVjNzU4IFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViNDUwIFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBBXHViYzg4IFx1ZDNmNFx1YzVkMFx1YzExYyBCXHViYzg4IFx1ZDNmNFx1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgXHVjNjJlXHVhZTMwXHViMjk0IFx1YWM4M1x1Yzc0NCBBQlx1Yjc3Y1x1YWNlMCBcdWQ0NWNcdWQ2MDRcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjYzBcdWQ2MTUgXHVkNTU4XHViMTc4XHVjNzc0XHViMjk0IFx1YmIzOFx1YzgxYyBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YzYyZVx1YWUzMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVjNzkwXHVhZTMwIFx1Yzc4NFx1Yzc1OFx1YzgwMVx1YzczY1x1Yjg1YyBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWM2MmVcdWFlMzBcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD48cD5cdTIwMjQgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWM1ZjBcdWMxOGRcdWM3M2NcdWI4NWMgXHViNDUwIFx1YmM4OCBcdWM2MmVcdWFlMzggXHVjMjE4IFx1YzVjNlx1YjJlNC48YnIgXC8+XHJcbiZuYnNwOyBcdTIwMjQgXHVjZDFkIFx1YzYyZVx1YWUzOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCA2XHVhYzAwXHVjOWMwKEFCLCBBQywgQkEsIEJDLCBDQSwgQ0IpXHVjNzc0XHVhY2UwIFx1Yzc3NCBcdWM1ZWNcdWMxMmYgXHVhYzAwXHVjOWMwXHVjNzU4IFx1YzYyZVx1YWUzMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOTg5LCAxXHViYzg4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3NCBcdWFkZjggXHVjOTExIFx1YzZiMFx1YzEyMFx1YzIxY1x1YzcwNFx1YWMwMCBcdWIxOTJcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1ZDBkZFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHViYjM4XHVjODFjXHViMjk0IFx1YzcwNCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViNTMwXHViNzdjIFx1ZDMxMFx1Yzc0NCBcdWM2MmVcdWFlMzggXHViNTRjIFx1YmFhOFx1YjRlMCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgQlx1ZDNmNFx1Yzc3NFx1YjA5OCBDXHVkM2Y0IFx1YzkxMSBcdWQ1NWMgXHVkM2Y0XHViODVjIFx1YmFhOFx1YjQ1MCBcdWM2MmVcdWFjYmNcdWM3NDQgXHViNTRjIFx1ZDY5Zlx1YzIxOFx1YWMwMCBcdWJhODcgXHViYzg4XHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIChcdWM3MDQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWM2MmVcdWFlMzBcdWIyZTQgXHViY2Y0XHViYTc0IFx1ZDU2ZFx1YzBjMSBcdWM1YjRcdWIyOTAgXHVkM2Y0XHViODVjIFx1YmFhOFx1YjQ1MCBcdWM2MmVcdWFjYThcdWM5YzRcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0Lik8XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI1MTRcdWMyYTRcdWQwNmNcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAzMClcdWFjZmMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCA2XHVhYzFjXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzZiMFx1YzEyMFx1YzIxY1x1YzcwNFx1YWMwMCBcdWIxOTJcdWM3NDAgXHVhYzgzXHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD4gXHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM3NzRcdWIzZDlcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NDAgMTBeMThcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIxLiAxXHViYzg4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBBLT5CXHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC5cclxuMi4gMlx1YmM4OCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgQS0+Q1x1Yjg1YyBcdWM2MmVcdWFlMzRcdWIyZTQuXHJcbjMuIDFcdWJjODggXHViNTE0XHVjMmE0XHVkMDZjXHViOTdjIEItPkFcdWI4NWMgXHVjNjJlXHVhZTM0XHViMmU0LlxyXG40LiAyXHViYzg4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBDLT5CXHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC5cclxuNS4gMVx1YmM4OCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgQS0+Qlx1Yjg1YyBcdWM2MmVcdWFlMzBcdWJhNzQgXHViMDVkXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIYW5vaSBUb3dlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSAmbGRxdW87SGFub2kgVG93ZXJzJnJkcXVvOyBwdXp6bGUgY29uc2lzdHMgb2YgdGhyZWUgcGVncyAodGhhdCB3ZSB3aWxsIG5hbWUgQSwgQiwgYW5kIEMpIHdpdGggbiBkaXNrcyBvZiBkaVx1ZmIwMGVyZW50IGRpYW1ldGVycyBzdGFja2VkIG9udG8gdGhlIHBlZ3MuIEluaXRpYWxseSBhbGwgZGlza3MgYXJlIHN0YWNrZWQgb250byBwZWcgQSB3aXRoIHRoZSBzbWFsbGVzdCBkaXNrIGF0IHRoZSB0b3AgYW5kIHRoZSBsYXJnZXN0IG9uZSBhdCB0aGUgYm90dG9tLCBzbyB0aGF0IHRoZXkgZm9ybSBhIGNvbmljYWwgc2hhcGUgb24gcGVnIEEuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaGFub2koMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTM1cHg7IHdpZHRoOjQwNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgdmFsaWQgbW92ZSBpbiB0aGUgcHV6emxlIGlzIG1vdmluZyBvbmUgZGlzayBmcm9tIHRoZSB0b3Agb2Ygb25lIChzb3VyY2UpIHBlZyB0byB0aGUgdG9wIG9mIHRoZSBvdGhlciAoZGVzdGluYXRpb24pIHBlZywgd2l0aCBhIGNvbnN0cmFpbnQgdGhhdCBhIGRpc2sgY2FuIGJlIHBsYWNlZCBvbmx5IG9udG8gYW4gZW1wdHkgZGVzdGluYXRpb24gcGVnIG9yIG9udG8gYSBkaXNrIG9mIGEgbGFyZ2VyIGRpYW1ldGVyLiBXZSBkZW5vdGUgYSBtb3ZlIHdpdGggdHdvIGNhcGl0YWwgbGV0dGVycyAmbWRhc2g7IHRoZSBcdWZiMDFyc3QgbGV0dGVyIGRlbm90ZXMgdGhlIHNvdXJjZSBkaXNrLCBhbmQgdGhlIHNlY29uZCBsZXR0ZXIgZGVub3RlcyB0aGUgZGVzdGluYXRpb24gZGlzay4gRm9yIGV4YW1wbGUsIEFCIGlzIGEgbW92ZSBmcm9tIGRpc2sgQSB0byBkaXNrIEIuPFwvcD5cclxuXHJcbjxwPlRoZSBwdXp6bGUgaXMgY29uc2lkZXJlZCBzb2x2ZWQgd2hlbiBhbGwgdGhlIGRpc2tzIGFyZSBzdGFja2VkIG9udG8gZWl0aGVyIHBlZyBCICh3aXRoIHBlZ3MgQSBhbmQgQyBlbXB0eSkgb3Igb250byBwZWcgQyAod2l0aCBwZWdzIEEgYW5kIEIgZW1wdHkpLiBXZSB3aWxsIHNvbHZlIHRoaXMgcHV6emxlIHdpdGggdGhlIGZvbGxvd2luZyBhbGdvcml0aG0uPFwvcD5cclxuXHJcbjxwPkFsbCBzaXggcG90ZW50aWFsIG1vdmVzIGluIHRoZSBnYW1lIChBQiwgQUMsIEJBLCBCQywgQ0EsIGFuZCBDQikgYXJlIGFycmFuZ2VkIGludG8gYSBsaXN0LiBUaGUgb3JkZXIgb2YgbW92ZXMgaW4gdGhpcyBsaXN0IGRlXHVmYjAxbmVzIG91ciBzdHJhdGVneS4gV2UgYWx3YXlzIG1ha2UgdGhlIFx1ZmIwMXJzdCB2YWxpZCBtb3ZlIGZyb20gdGhpcyBsaXN0IHdpdGggYW4gYWRkaXRpb25hbCBjb25zdHJhaW50IHRoYXQgd2UgbmV2ZXIgbW92ZSB0aGUgc2FtZSBkaXNrIHR3aWNlIGluIGEgcm93LjxcL3A+XHJcblxyXG48cD5JdCBjYW4gYmUgcHJvdmVuIHRoYXQgdGhpcyBhbGdvcml0aG0gYWx3YXlzIHNvbHZlcyB0aGUgcHV6emxlLiBZb3VyIHByb2JsZW0gaXMgdG8gXHVmYjAxbmQgdGhlIG51bWJlciBvZiBtb3ZlcyBpdCB0YWtlcyBmb3IgdGhpcyBhbGdvcml0aG0gdG8gc29sdmUgdGhlIHB1enpsZSB1c2luZyBhIGdpdmVuIHN0cmF0ZWd5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIHR3byBsaW5lcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gKDEgJmxlOyBuICZsZTsgMzApICZuZGFzaDsgdGhlIG51bWJlciBvZiBkaXNrcyBpbiB0aGUgcHV6emxlLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgZGVzY3JpcHRpb25zIG9mIHNpeCBtb3ZlcyBzZXBhcmF0ZWQgYnkgc3BhY2VzICZtZGFzaDsgdGhlIHN0cmF0ZWd5IHRoYXQgaXMgdXNlZCB0byBzb2x2ZSB0aGUgcHV6emxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPldyaXRlIHRvIHRoZSBvdXRwdXQgXHVmYjAxbGUgdGhlIG51bWJlciBvZiBtb3ZlcyBpdCB0YWtlcyB0byBzb2x2ZSB0aGUgcHV6emxlLiBUaGlzIG51bWJlciB3aWxsIG5vdCBleGNlZWQgMTA8c3VwPjE4PFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=
