시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1528 655 515 44.320%

문제

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjE3MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2MgXHVjZjU0XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD4yJnRpbWVzO04gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YjExM1x1Yzc0MCBcdWQzMTBcdWM3NDQgMSZ0aW1lczsyIChcdWI2MTBcdWIyOTQgMiZ0aW1lczsxKSBcdWQwNmNcdWFlMzBcdWM2NDAgMiZ0aW1lczsyIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWQwYzBcdWM3N2NcdWI4NWMgXHVjYzQ0XHVjNmIwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsIFx1YWMwMVx1YWMwMVx1Yzc0NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjZjU0XHViNGRjXHViODVjIFx1YjMwMFx1Yzc1MVx1YzJkY1x1Y2YxY1x1YzExYyBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWM1ZDAgXHVjNzc0XHVjNmE5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWMwZGRcdWFjYmNcdWIyZTQuIFx1YjExM1x1Yzc0MCBcdWQzMTBcdWM3NDQgXHVhZDUwXHVkNjU4XHVkNTU4XHViMmU0IFx1YmNmNFx1YjJjOCBcdWM4OGNcdWM2YjAgXHViMzAwXHVjZTZkXHVjNzc4IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWM1YjQsIFx1YjRhNFx1YzlkMVx1ZDc4OFx1YjI5NCBcdWFjYmRcdWM2YjAgXHVjZjU0XHViNGRjXHVhYzAwIFx1ZDVmN1x1YWMwOFx1YjlhY1x1YWM4YyBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNTQ0XHViNzk4XHVjNzU4IFx1YjQ1MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHViMmVjXHViNzdjIFx1YmNmNFx1Yzc3NFx1YzljMFx1YjljYyBcdWM4OGNcdWM2YjAgXHViMzAwXHVjZTZkXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3hrZGxmLlBOR1wiIHN0eWxlPVwiaGVpZ2h0OjIwOHB4OyB3aWR0aDoyNTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5OXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVjODA0XHVjY2I0IFx1ZDBjMFx1Yzc3YyBcdWNmNTRcdWI0ZGNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiAoXHViMmU4LCBcdWMxMWNcdWI4NWMgXHVjODhjXHVjNmIwIFx1YjMwMFx1Y2U2ZFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjOTExXHViY2Y1XHViNDFjIFx1ZDQ1Y1x1ZDYwNFx1Yzc0MCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1Yjg1Y1x1YjljYyBcdWNjOThcdWI5YWNcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQwYzBcdWM3N2NcdWM3NTggXHVkMDZjXHVhZTMwIE4oMSZsZTtOJmxlOzMwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQwYzBcdWM3N2MgXHVjZjU0XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTcyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRpbGUgQ29kZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNpdHkgb2YgU29uZ3BhIGlzIG5vdyBjYXJyeWluZyBvdXQgYSBwcm9qZWN0IHRvIGJ1aWxkIGEgYmljeWNsZSB0cmFuc3BvcnRhdGlvbiBzeXN0ZW0gY2FsbGVkICZsc3F1bztncmVlbiBTb25ncGEuJnJzcXVvOyBCeSB0aGUgZW5kIG9mIHRoaXMgeWVhciwgY2l0aXplbnMgYW5kIHZpc2l0b3JzIGFsaWtlIHdpbGwgYmUgYWJsZSB0byBwaWNrIHVwIGFuZCBkcm9wIG9mZiBiaWN5Y2xlcyB0aHJvdWdob3V0IHRoZSBjaXR5LiBSZWNlbnRseSwgaXQgd2FzIGRlY2lkZWQgdG8gYXR0YWNoIGEgbnVtYmVyIHRhZyB0byBlYWNoIGJpY3ljbGUgZm9yIG1hbmFnZW1lbnQgdXNlLiBUaGUgYmljeWNsZXMgd2lsbCBiZSB1bmRlciBjb250cm9sIG9mIHRoZSBjaXR5JnJzcXVvO3MgdHJhZmZpYyBzeXN0ZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBudW1iZXIgdGFnIGNvbnRhaW5zIGEgdGlsZSBjb2RlIG9mIGxlbmd0aCBuICwgd2hpY2ggY29uc2lzdHMgb2YgMSZ0aW1lczsyICwgMiZ0aW1lczsxLCBhbmQgMiZ0aW1lczsyIHRpbGVzIHBsYWNlZCBvbiBhIDImdGltZXM7IG4gcmVjdGFuZ3VsYXIgcGxhdGUgaW4gYSB3YXkgdGhhdCBldmVyeSBjZWxsIG9mIHRoZSBwbGF0ZSBpcyBjb3ZlcmVkIGJ5IGV4YWN0bHkgb25lIHRpbGUuIFRoZSBwbGF0ZSBpcyBkaXZpZGVkIGludG8gMm4gY2VsbHMgb2Ygc2l6ZTEmdGltZXM7MS4gT2YgY291cnNlLCBubyB0d28gdGlsZXMgYXJlIGFsbG93ZWQgdG8gb3ZlcmxhcCBlYWNoIG90aGVyLiBUaGUgMiZ0aW1lczs1IHBsYXRlIGFuZCBhIHRpbGUgY29kZSBvZiBsZW5ndGggNSBhcmUgc2hvd24gaW4gRmlndXJlcyAxIGFuZCAyLCByZXNwZWN0aXZlbHkuIFRoZSBjb2RlIHdpbGwgYWx3YXlzIGJlIHJlYWQgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBIb3dldmVyLCB0aGVyZSBpcyBubyBkaXN0aW5jdGlvbiBiZXR3ZWVuIHRoZSB0b3Agc2lkZSBhbmQgdGhlIGJvdHRvbSBzaWRlIG9mIHRoZSBjb2RlLiBUaGUgY29kZSBtYXkgYmUgdHVybmVkIHVwc2lkZSBkb3duLiBUaGUgY29kZSBzaG93biBpbiBGaWd1cmUgMyBpcyBlc3NlbnRpYWxseSB0aGUgc2FtZSBjb2RlIGFzIGluIEZpZ3VyZSAyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RpbGVjb2RlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMXB4OyB3aWR0aDo2MzhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHBvc2l0aXZlIGludGVnZXIgbiAsIHRoZSBwcm9qZWN0IGRpcmVjdG9yIERyLiBZYW5nIHdhbnRzIHRvIGtub3cgaG93IG1hbnkgdGlsZSBjb2RlcyBvZiBsZW5ndGggbiB0aGVyZSBhcmUsIHRoYXQgaXMsIHRoZSBudW1iZXIgb2Ygd2F5cyB0byBwbGFjZSB0aGUgdGhyZWUga2luZHMgb2YgdGlsZXMgaW50byBhIDImdGltZXM7biByZWN0YW5ndWxhciBwbGF0ZSBzdWJqZWN0IHRvIHRoZSBhYm92ZSBjb25kaXRpb25zLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYW4gaGVscCBoaW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgaXMgZ2l2ZW4gaW4gYSBzaW5nbGUgbGluZSwgd2hpY2ggY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIG4gLCAxJm5ic3A7JmxlOyBuICZsZTsgMzAgLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHRpbGUgY29kZXMgb2YgbGVuZ3RoIG4gLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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