2726번 - 삼각 N-Queen 스페셜 저지다국어

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

문제

한 변에 N칸이 있는 삼각형 모양의 체스판이 있다. 이 체스판에서 퀸은 변과 평행하면서 퀸을 포함하는 줄의 모든 칸을 공격할 수 있다. 예를 들어, 아래 그림에서 검정색 칸이 퀸일때, 퀸이 공격할 수 있는 칸을 표시해 놓은 것이다.

삼각 N-Queen 문제는 한 변에 N칸이 있는 삼각형 체스판에서 퀸을 서로 공격할 수 없게 최대한 배치하는 것이다. 아래 그림은 N=6일때, 퀸을 서로 공격할 수 없게 최대한 배치한 것이다.

삼각형 한 변의 칸의 수가 N이면, 항상 floor((2*N+1)/3)개의 퀸을 서로 공격할 수 없게 배치할 수 있다.

N이 주어졌을 때, 삼각 N-Queen문제를 푸는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 C(1 ≤ C ≤ 1000)가 주어진다. 각 테스트 케이스는 N(1 ≤ N ≤ 1000)을 포함하고 있으며, 한 줄로 이루어져 있다.

출력

각 테스트 케이스에 대해서, 첫 줄에 놓을 수 있는 퀸의 최대 개수를 출력한다. 둘째 줄부터 N개의 줄에는 퀸의 위치를 출력한다. 제일 윗 줄의 번호는 1이고, 그 줄의 가장 왼쪽 칸의 번호는 1이다. 위치는 줄 번호와 열 번호를 공백으로 구분해서 한 줄에 하나씩 출력하면 된다. 가능한 배치가 여러 가지인 경우에는 아무거나 출력하면 된다.

예제 입력 1 

6
3
6
9
10
14
18

예제 출력 1 

2
1 1
3 2
4
3 1
4 3
5 5
6 2
6
4 1
5 3
6 5
7 7
8 2
9 4
7
4 1
5 3
6 5
7 7
8 2
9 4
10 6
9
6 1
7 3
8 5
9 7
10 9
11 11
12 2
13 4
14 6
12
7 1
8 3
9 5
10 7
11 9
12 11
13 13
14 2
15 4
16 6
17 8
18 10
W3sicHJvYmxlbV9pZCI6IjI3MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDEgTi1RdWVlbiIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVkNTVjIFx1YmNjMFx1YzVkMCBOXHVjZTc4XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWMwYmNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDBcdWMxMWMgXHVkMDM4XHVjNzQwIFx1YmNjMFx1YWNmYyBcdWQzYzlcdWQ1ODlcdWQ1NThcdWJhNzRcdWMxMWMgXHVkMDM4XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWM5MDRcdWM3NTggXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0NCBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWFjODBcdWM4MTVcdWMwYzkgXHVjZTc4XHVjNzc0IFx1ZDAzOFx1Yzc3Y1x1YjU0YywgXHVkMDM4XHVjNzc0IFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc0NCBcdWQ0NWNcdWMyZGNcdWQ1NzQgXHViMTkzXHVjNzQwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ucTEucG5nXCIgc3R5bGU9XCJ3aWR0aDogMjgwcHg7IGhlaWdodDogMjQ0cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBiY1x1YWMwMSBOLVF1ZWVuIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWQ1NWMgXHViY2MwXHVjNWQwIE5cdWNlNzhcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNSBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDBcdWMxMWMgXHVkMDM4XHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWM4YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBOPTZcdWM3N2NcdWI1NGMsIFx1ZDAzOFx1Yzc0NCBcdWMxMWNcdWI4NWMgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWFjOGMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmMzMFx1Y2U1OFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbnEyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDI3N3B4OyBoZWlnaHQ6IDI0NXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYmNcdWFjMDFcdWQ2MTUgXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWNlNzhcdWM3NTggXHVjMjE4XHVhYzAwIE5cdWM3NzRcdWJhNzQsIFx1ZDU2ZFx1YzBjMSBmbG9vcigoMipOKzEpXC8zKVx1YWMxY1x1Yzc1OCBcdWQwMzhcdWM3NDQgXHVjMTFjXHViODVjIFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHROXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBiY1x1YWMwMSBOLVF1ZWVuXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBDKDEgJmxlOyBDICZsZTsgMTAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBOKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjY2FiIFx1YzkwNFx1YzVkMCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQwMzhcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMDM4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWM3MTcgXHVjOTA0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHVjNzc0XHVhY2UwLCBcdWFkZjggXHVjOTA0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjZTc4XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWM3MDRcdWNlNThcdWIyOTQgXHVjOTA0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWM1ZjQgXHViYzg4XHVkNjM4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzRcdWMxMWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzI2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJpYW5ndWxhciBOLVF1ZWVucyBQcm9ibGVtIiwiZGVzY3JpcHRpb24iOiI8cD5BICZsZHF1bztxdWVlbiZyZHF1bzsgcGllY2Ugb24gYSB0cmlhbmd1bGFyIGFycmF5IG9mIGNlbGxzLCBOIGNlbGxzIG9uIGEgc2lkZSwgY2FuIGF0dGFjayBhbnkgY2VsbCBvbiBhIGZpbGUgcGFyYWxsZWwgdG8gb25lIG9mIHRoZSBzaWRlcyBjb250YWluaW5nIHRoZSBxdWVlbiZyc3F1bztzIGNlbGwuIEZvciBleGFtcGxlLCBpbiB0aGUgYXJyYXkgaW4gRmlndXJlIDEsIGEgcXVlZW4gb24gdGhlIGJsYWNrIGNlbGwsIGF0dGFja3MgYWxsIG9mIHRoZSBzaGFkZWQgY2VsbHMuIFRoZSBUcmlhbmd1bGFyIE5RdWVlbnMgUHJvYmxlbSBvZiBzaXplIE4sIGlzIHRvIGZpbmQgYSBtYXhpbWFsIHNldCBvZiBxdWVlbiBwb3NpdGlvbnMgaW4gYSB0cmlhbmd1bGFyIGFycmF5IHdpdGggTiBjZWxscyBvbiBhIHNpZGUgc28gdGhhdCBubyBxdWVlbiBpcyBhdHRhY2tpbmcgYW55IG90aGVyIHF1ZWVuLiBGb3IgZXhhbXBsZSx0aGUgYmxhY2sgY2VsbHMgaW4gRmlndXJlIDIgZ2l2ZSBhIG1heGltYWwgc2V0IG9mIHF1ZWVuIHBvc2l0aW9ucyBpbiBhIHNpemUgNiBhcnJheS4gSXQgdHVybnMgb3V0IHRoYXQgYSBzaXplIE4gYXJyYXkgYWx3YXlzIGhhcyBmbG9vcigoMipOICsgMSlcLzMpIGFzIHRoZSBtYXhpbWFsIG51bWJlciBvZiBub24tYXR0YWNraW5nIHF1ZWVuIHBvc2l0aW9ucy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cXVlZW4ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjY0cHg7IHdpZHRoOjU5M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSwgd2hpY2gsIGdpdmVuIHRoZSBzaXplLCBOLCBvZiB0aGUgdHJpYW5ndWxhciBhcnJheSwgZmluZHMgYSBtYXhpbWFsIHNldCBvZiBub24tYXR0YWNraW5nIHF1ZWVuIHBvc2l0aW9ucyBvbiB0aGUgYXJyYXkgKGZsb29yKCgyKk4gKyAxKVwvMykgb2YgdGhlbSkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciB2YWx1ZSBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgZGF0YXNldHMgdGhhdCBmb2xsb3csIEMsICgxICZsZTsgQyAmbGU7IDEwMDApLiBFYWNoIGRhdGFzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBzaXplIG9mIHRoZSB0cmlhbmd1bGFyIGFycmF5LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBvdXRwdXQgbGluZSBmb3IgZWFjaCBwcm9ibGVtIGdpdmVzIHRoZSBwcm9ibGVtIG51bWJlciBzdGFydGluZyBhdCAxLCBhIHNpbmdsZSBzcGFjZSwgdGhlIGlucHV0IHNpemUsIGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgbnVtYmVyIG9mIHF1ZWVuIHBvc2l0aW9ucy4gRm9sbG93aW5nIHRoZSBmaXJzdCBsaW5lIHdpbGwgYmUgdGhlIHF1ZWVuIHBvc2l0aW9ucywgOCBwb3NpdGlvbnMgcGVyIGxpbmUgZXhjZXB0IHBlcmhhcHMgZm9yIHRoZSBsYXN0IGxpbmUgb2YgcG9zaXRpb25zLiBFYWNoIHBvc2l0aW9uIGhhcyB0aGUgZm9ybWF0IG9wZW4gYnJhY2tldCAoJmxzcXVvO1smbHNxdW87KSwgcm93IG51bWJlciBzdGFydGluZyB3aXRoIDEsIGEgY29tbWEsIHRoZSBwb3NpdGlvbiBmcm9tIHRoZSBsZWZ0IHdpdGhpbiB0aGUgcm93IHN0YXJ0aW5nIGF0IDEgYW5kIGEgY2xvc2UgYnJhY2tldCAoJmxzcXVvO10mcnNxdW87KS4gUG9zaXRpb25zIHdpdGhpbiBhIGxpbmUgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gRm9yIGV4YW1wbGUsIHRoZSBxdWVlbiBwb3NpdGlvbnMgaW4gRmlndXJlIDIgYXJlIFsxLDFdIFs0LDJdIFs1LDRdIFs2LDNdLiBUaGUgbGluZXMgb2YgcG9zaXRpb24gdmFsdWVzIGFyZSBmb2xsb3dlZCBieSBhIHNpbmdsZSBibGFuayBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiI8b2w+XHJcblx0PGxpPlRoZXJlIG1heSBiZSBtYW55IGRpZmZlcmVudCBjb3JyZWN0IGFuc3dlcnMgdG8gYSBwYXJ0aWN1bGFyIHByb2JsZW0sIHNvIHlvdXIgYW5zd2VycyBuZWVkIG5vdCBiZSB0aGUgc2FtZSBhcyB0aG9zZSBpbiB0aGUgU2FtcGxlIE91dHB1dCBhYm92ZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+U29tZSBzb2x1dGlvbiBtZXRob2RzIGZvciB0aGlzIHByb2JsZW0gbWF5IGNhdXNlIHRoZSB0aW1lIGxpbWl0IHRvIGJlIGV4Y2VlZGVkLiBCZSBzdXJlIHRvIHRyeSB0aGUgbGFyZ2VyIHZhbHVlcyBiZWZvcmUgc3VibWl0dGluZyB5b3VyIHNvbHV0aW9uPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > Greater New York Region > 2006 Greater New York Programming Contest G번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)