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

문제

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

  1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
  2. 정사각형의 중심에 점을 하나 추가한다.

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

초기 상태 - 점 4개 1번 - 점 9개 2번 - 25개

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다. 과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

출력

첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

25

예제 입력 3

5

예제 출력 3

1089
W3sicHJvYmxlbV9pZCI6IjI5MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5MTFcdWM1NTkgXHVjNzc0XHViM2Q5IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWQ1NjhcdWFlZDggU0ZcdWM2MDFcdWQ2NTRcdWI5N2MgXHVjYzBkXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzYwMVx1ZDY1NFx1YjI5NCBcdWM2NzhcdWFjYzQgXHVjOWMwXHVkNjE1XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHVjMmU0XHVjODFjXHViODVjIFx1YzZiMFx1YzhmY1x1YzEyMFx1Yzc0NCBcdWQwYzBcdWFjZTAgXHVjNjc4XHVhY2M0IFx1ZDU4OVx1YzEzMVx1YzVkMCBcdWFjMDBcdWMxMWMgXHVjZDJjXHVjNjAxXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjZWY0XHVkNGU4XHVkMTMwIFx1YWRmOFx1Yjc5OFx1ZDUzZFx1YzczY1x1Yjg1YyBDR1x1Y2M5OFx1YjlhY1x1Yjk3YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2NzhcdWFjYzQgXHVjOWMwXHVkNjE1XHVjNzQwIFx1YzkxMVx1YzU1OSBcdWM3NzRcdWIzZDkgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzgxMCA0XHVhYzFjXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1ZDZjNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNjZDBcdWMxMWMgXHVjOWMwXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzAxIFx1YmNjMFx1Yzc1OCBcdWM5MTFcdWM1NTlcdWM1ZDAgXHVjODEwXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM1ZDAgXHVjODEwXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOTRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YWM3MFx1Y2U1OFx1YmE3NCBcdWNkMWQgNFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjMGM4XHViODVjIFx1YzBkZFx1YWUzNFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMgXHVhZTRjXHVjOWMwIFx1YWNjNFx1YzE4ZFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjZDFkIDJcdWJjODggXHVhYzcwXHVjY2U0XHVjNzQ0IFx1YjU0Y1x1YWU0Y1x1YzljMFx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRkLWNlbnRlclwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNWU0NDZmMGYtNjEzYy00Y2UwLWE2MjYtNmIwYzI3MjllZDFlXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTRweDsgaGVpZ2h0OiAyMTNweDtcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNjVjMWJjZjEtN2Q4YS00NjNiLTkxZGYtZDZjYWJjYzJjZWFlXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTJweDsgaGVpZ2h0OiAyMTNweDtcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMjdiOTk0NjctY2ZkZi00Y2UzLWEwYjAtMjg5Nzc0N2VkY2Y5XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTJweDsgaGVpZ2h0OiAyMTNweDtcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkYyAtIFx1YzgxMCA0XHVhYzFjPFwvdGQ+XHJcblx0XHRcdDx0ZD4xXHViYzg4IC0gXHVjODEwIDlcdWFjMWM8XC90ZD5cclxuXHRcdFx0PHRkPjJcdWJjODggLSAyNVx1YWMxYzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzViNFx1YjVhNCBcdWM4MTBcdWM3NDAgXHVkNTVjIFx1YWMxYyBcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVjNTU4XHViMmU0LiBcdWJhNTRcdWJhYThcdWI5YWMgXHVjMThjXHViYWE4XHViN2M5XHVjNzQ0IFx1YzkwNFx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjOTExXHViY2Y1XHVkNTU4XHViMjk0IFx1YzgxMFx1Yzc0NCBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWNmY1x1YzgxNVx1Yzc0NCBOXHViYzg4IFx1YWM3MFx1Y2U1YyBcdWQ2YzQgXHVjODEwIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDE1KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2ZjXHVjODE1XHVjNzQ0IE5cdWJjODggXHVhYzcwXHVjZTVjIFx1ZDZjNCZuYnNwO1x1YzgxMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTEFOSU5BIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBmaWxtaW5nIGEgbW92aWUgYWRhcHRhdGlvbiBvZiB0aGUgcG9wdWxhciBTRiBub3ZlbCAmcXVvdDtDaGlja3MgaW4gc3BhY2UgMTMmcXVvdDsuIFRoZSBzY3JpcHQgcmVxdWlyZXMgdGhlbSB0byBwcmVzZW50IGEgbG90IG9mIGRpZmZlcmVudCB3b3JsZHMgc28gdGhleSBkZWNpZGVkIHRvIGZpbG0gdGhlIGVudGlyZSBtb3ZpZSBpbiBmcm9udCBvZiBhIGdyZWVuIHNjcmVlbiBhbmQgYWRkIENHSSBiYWNrZ3JvdW5kcyBsYXRlci4gTWlya28gaGVhcmQgdGhhdCB0aGUgYmVzdCB3YXkgdG8gZ2VuZXJhdGUgYXJ0aWZpY2lhbCB0ZXJyYWluIGlzIHRvIHVzZSBtaWRwb2ludCBkaXNwbGFjZW1lbnQgYWxnb3JpdGhtLjxcL3A+XHJcblxyXG48cD5UbyBzdGFydCB0aGUgYWxnb3JpdGhtLCBNaXJrbyBzZWxlY3RzIDQgcG9pbnRzIGZvcm1pbmcgYSBwZXJmZWN0IHNxdWFyZS4gSGUgdGhlbiBwZXJmb3JtcyB0aGUgZm9sbG93aW5nIHN0ZXBzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPk9uIGVhY2ggc2lkZSBvZiB0aGUgc3F1YXJlLCBoZSBhZGRzIGEgbmV3IHBvaW50IGluIHRoZSBleGFjdCBtaWRkbGUgb2YgdGhlIHNpZGUuIFRoZSBoZWlnaHQgb2YgdGhpcyBuZXcgcG9pbnQgaXMgdGhlIGF2ZXJhZ2UgaGVpZ2h0IG9mIHRoZSB0d28gcG9pbnRzIG9uIHRoYXQgc2lkZS48XC9saT5cclxuXHQ8bGk+SW4gdGhlIGV4YWN0IGNlbnRlciBvZiB0aGUgc3F1YXJlIGhlIGFkZHMgYSBuZXcgcG9pbnQgd2hvc2UgaGVpZ2h0IGlzIHRoZSBhdmVyYWdlIGhlaWdodCBvZiBhbGwgNCBzcXVhcmUgdmVydGljZXMsIHBsdXMgYSBzbWFsbCByYW5kb20gdmFsdWUuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QWZ0ZXIgdGhvc2UgdHdvIHN0ZXBzIGFyZSBwZXJmb3JtZWQsIGhlIG5vdyBoYXMgNCBuZXcgc3F1YXJlcy4gSGUgcGVyZm9ybXMgdGhlIHNhbWUgc3RlcHMgb24gdGhlIG5ld2x5IGNyZWF0ZWQgc3F1YXJlcyBhZ2FpbiBhbmQgYWdhaW4gdW50aWwgaGUgaXMgcGxlYXNlZCB3aXRoIHRoZSByZXN1bHRzLiBUaGUgZm9sbG93aW5nIGRpYWdyYW0gaWxsdXN0cmF0ZXMgMiBpdGVyYXRpb25zIG9mIHRoZSBhbGdvcml0aG0uPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRkLWNlbnRlclwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNWU0NDZmMGYtNjEzYy00Y2UwLWE2MjYtNmIwYzI3MjllZDFlXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTRweDsgaGVpZ2h0OiAyMTNweDtcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNjVjMWJjZjEtN2Q4YS00NjNiLTkxZGYtZDZjYWJjYzJjZWFlXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTJweDsgaGVpZ2h0OiAyMTNweDtcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMjdiOTk0NjctY2ZkZi00Y2UzLWEwYjAtMjg5Nzc0N2VkY2Y5XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTJweDsgaGVpZ2h0OiAyMTNweDtcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+U3RhcnQgLSA0IHBvaW50czxcL3RkPlxyXG5cdFx0XHQ8dGQ+MSBpdGVyYXRpb24gLSA5IHBvaW50czxcL3RkPlxyXG5cdFx0XHQ8dGQ+MiBpdGVyYXRpb25zIC0gMjUgcG9pbnRzPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5NaXJrbyBub3RpY2VkIHRoYXQgc29tZSBvZiB0aGUgcG9pbnRzIGJlbG9uZyB0byBtb3JlIHRoYW4gb25lIHNxdWFyZS4gSW4gb3JkZXIgdG8gZGVjcmVhc2UgbWVtb3J5IGNvbnN1bXB0aW9uLCBoZSBzdG9yZXMgY2FsY3VsYXRlcyBhbmQgc3RvcmVzIHN1Y2ggcG9pbnRzIG9ubHkgb25jZS4gSGUgbm93IHdvbmRlcnMgaG93IG1hbnkgcG9pbnRzIGluIHRvdGFsIHdpbGwgaGUgbmVlZCB0byBzdG9yZSBpbiBtZW1vcnkgYWZ0ZXIgTiBpdGVyYXRpb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxNSksIG51bWJlciBvZiBpdGVyYXRpb25zPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBudW1iZXIsIHRoZSBudW1iZXIgb2YgcG9pbnRzIHN0b3JlZCBhZnRlciBOIGl0ZXJhdGlvbnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #4 2번

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