시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB31171311104343.099%

문제

2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다.

그런데 문제가 생겼다. 넓은 판을 교환하다 보니 좌우 대칭인 경우가 있어, 뒤집히는 경우 코드가 헷갈리게 되는 경우가 발생한 것이다. 예를 들어 아래의 두 경우는 달라 보이지만 좌우 대칭을 이루고 있다.

N이 주어지면, 전체 타일 코드의 개수를 구하는 프로그램을 작성하시오. (단, 서로 좌우 대칭을 이루는 중복된 표현은 한 가지 경우로만 처리한다.)

입력

첫째 줄에 타일의 크기 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 타일 코드의 개수를 출력한다.

예제 입력 1

4

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjE3MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2MgXHVjZjU0XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD4yJnRpbWVzO04gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YjExM1x1Yzc0MCBcdWQzMTBcdWM3NDQgMSZ0aW1lczsyIChcdWI2MTBcdWIyOTQgMiZ0aW1lczsxKSBcdWQwNmNcdWFlMzBcdWM2NDAgMiZ0aW1lczsyIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQwYzBcdWM3N2NcdWI4NWMgXHVjYzQ0XHVjNmIwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsIFx1YWMwMVx1YWMwMVx1Yzc0NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjZjU0XHViNGRjXHViODVjIFx1YjMwMFx1Yzc1MVx1YzJkY1x1Y2YxY1x1YzExYyBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWM1ZDAgXHVjNzc0XHVjNmE5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWMwZGRcdWFjYmNcdWIyZTQuIFx1YjExM1x1Yzc0MCBcdWQzMTBcdWM3NDQgXHVhZDUwXHVkNjU4XHVkNTU4XHViMmU0IFx1YmNmNFx1YjJjOCBcdWM4OGNcdWM2YjAgXHViMzAwXHVjZTZkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWM1YjQsIFx1YjRhNFx1YzlkMVx1ZDc4OFx1YjI5NCBcdWFjYmRcdWM2YjAgXHVjZjU0XHViNGRjXHVhYzAwIFx1ZDVmN1x1YWMwOFx1YjlhY1x1YWM4YyBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNTQ0XHViNzk4XHVjNzU4IFx1YjQ1MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHViMmVjXHViNzdjIFx1YmNmNFx1Yzc3NFx1YzljMFx1YjljYyBcdWM4OGNcdWM2YjAgXHViMzAwXHVjZTZkXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3hrZGxmLlBOR1wiIHN0eWxlPVwiaGVpZ2h0OjIwOHB4OyB3aWR0aDoyNTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5OXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjODA0XHVjY2I0IFx1ZDBjMFx1Yzc3YyBcdWNmNTRcdWI0ZGNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiAoXHViMmU4LCBcdWMxMWNcdWI4NWMgXHVjODhjXHVjNmIwIFx1YjMwMFx1Y2U2ZFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjOTExXHViY2Y1XHViNDFjIFx1ZDQ1Y1x1ZDYwNFx1Yzc0MCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1Yjg1Y1x1YjljYyBcdWNjOThcdWI5YWNcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQwYzBcdWM3N2NcdWM3NTggXHVkMDZjXHVhZTMwIE4oMSAmbGU7IE4gJmxlOyAzMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGMwXHVjNzdjIFx1Y2Y1NFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaWxlIENvZGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjaXR5IG9mIFNvbmdwYSBpcyBub3cgY2Fycnlpbmcgb3V0IGEgcHJvamVjdCB0byBidWlsZCBhIGJpY3ljbGUgdHJhbnNwb3J0YXRpb24gc3lzdGVtIGNhbGxlZCAmbHNxdW87Z3JlZW4gU29uZ3BhLiZyc3F1bzsgQnkgdGhlIGVuZCBvZiB0aGlzIHllYXIsIGNpdGl6ZW5zIGFuZCB2aXNpdG9ycyBhbGlrZSB3aWxsIGJlIGFibGUgdG8gcGljayB1cCBhbmQgZHJvcCBvZmYgYmljeWNsZXMgdGhyb3VnaG91dCB0aGUgY2l0eS4gUmVjZW50bHksIGl0IHdhcyBkZWNpZGVkIHRvIGF0dGFjaCBhIG51bWJlciB0YWcgdG8gZWFjaCBiaWN5Y2xlIGZvciBtYW5hZ2VtZW50IHVzZS4gVGhlIGJpY3ljbGVzIHdpbGwgYmUgdW5kZXIgY29udHJvbCBvZiB0aGUgY2l0eSZyc3F1bztzIHRyYWZmaWMgc3lzdGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbnVtYmVyIHRhZyBjb250YWlucyBhIHRpbGUgY29kZSBvZiBsZW5ndGggbiAsIHdoaWNoIGNvbnNpc3RzIG9mIDEmdGltZXM7MiAsIDImdGltZXM7MSwgYW5kIDImdGltZXM7MiB0aWxlcyBwbGFjZWQgb24gYSAyJnRpbWVzOyBuIHJlY3Rhbmd1bGFyIHBsYXRlIGluIGEgd2F5IHRoYXQgZXZlcnkgY2VsbCBvZiB0aGUgcGxhdGUgaXMgY292ZXJlZCBieSBleGFjdGx5IG9uZSB0aWxlLiBUaGUgcGxhdGUgaXMgZGl2aWRlZCBpbnRvIDJuIGNlbGxzIG9mIHNpemUxJnRpbWVzOzEuIE9mIGNvdXJzZSwgbm8gdHdvIHRpbGVzIGFyZSBhbGxvd2VkIHRvIG92ZXJsYXAgZWFjaCBvdGhlci4gVGhlIDImdGltZXM7NSBwbGF0ZSBhbmQgYSB0aWxlIGNvZGUgb2YgbGVuZ3RoIDUgYXJlIHNob3duIGluIEZpZ3VyZXMgMSBhbmQgMiwgcmVzcGVjdGl2ZWx5LiBUaGUgY29kZSB3aWxsIGFsd2F5cyBiZSByZWFkIGZyb20gbGVmdCB0byByaWdodC4gSG93ZXZlciwgdGhlcmUgaXMgbm8gZGlzdGluY3Rpb24gYmV0d2VlbiB0aGUgdG9wIHNpZGUgYW5kIHRoZSBib3R0b20gc2lkZSBvZiB0aGUgY29kZS4gVGhlIGNvZGUgbWF5IGJlIHR1cm5lZCB1cHNpZGUgZG93bi4gVGhlIGNvZGUgc2hvd24gaW4gRmlndXJlIDMgaXMgZXNzZW50aWFsbHkgdGhlIHNhbWUgY29kZSBhcyBpbiBGaWd1cmUgMi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90aWxlY29kZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjFweDsgd2lkdGg6NjM4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwb3NpdGl2ZSBpbnRlZ2VyIG4gLCB0aGUgcHJvamVjdCBkaXJlY3RvciBEci4gWWFuZyB3YW50cyB0byBrbm93IGhvdyBtYW55IHRpbGUgY29kZXMgb2YgbGVuZ3RoIG4gdGhlcmUgYXJlLCB0aGF0IGlzLCB0aGUgbnVtYmVyIG9mIHdheXMgdG8gcGxhY2UgdGhlIHRocmVlIGtpbmRzIG9mIHRpbGVzIGludG8gYSAyJnRpbWVzO24gcmVjdGFuZ3VsYXIgcGxhdGUgc3ViamVjdCB0byB0aGUgYWJvdmUgY29uZGl0aW9ucy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FuIGhlbHAgaGltLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFRpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGlzIGdpdmVuIGluIGEgc2luZ2xlIGxpbmUsIHdoaWNoIGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBuICwgMSZuYnNwOyZsZTsgbiAmbGU7IDMwIC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiB0aWxlIGNvZGVzIG9mIGxlbmd0aCBuIC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2007 E번

  • 문제를 번역한 사람: author5
  • 문제의 오타를 찾은 사람: kthng
  • 어색한 표현을 찾은 사람: plzrun