온실 화분 배치
문제
한 변의 칸 수가 N인 정사각형 모양의 온실이 있다. 온실의 바닥은 N개의 행과 N개의 열로 나뉘어 있고, 각 칸에는 화분을 하나씩 놓을 수 있다. 행 번호는 위쪽부터, 열 번호는 왼쪽부터 1번씩 센다.
이 온실에서 기르는 화분은 향이 매우 강한 품종이다. 온실의 환풍기는 행 방향과 열 방향, 그리고 네 개의 대각선 방향으로 바람을 보낸다. 그래서 두 화분이 같은 행에 있거나, 같은 열에 있거나, 같은 대각선 위에 있으면 두 화분의 향이 서로 섞인다. 두 화분이 같은 대각선 위에 있다는 말은 두 화분의 행 번호 차이와 열 번호 차이가 서로 같다는 뜻이다. 예를 들어 2행 3열의 화분과 4행 5열의 화분은 행 번호 차이가 2이고 열 번호 차이도 2이므로 같은 대각선 위에 있다. 향이 섞인 화분은 상품으로 팔 수 없다.
관리인은 향이 하나도 섞이지 않는 상태로 화분 N개를 온실에 모두 놓고 싶다. 온실의 한 변의 칸 수 N이 주어졌을 때, 화분 N개를 놓는 서로 다른 방법의 수를 계산하는 프로그램을 작성하여라. 화분은 모두 같은 품종이라 서로 구별하지 않으며, 화분이 놓인 칸의 모임이 다르면 서로 다른 방법으로 센다.
예를 들어 N=4인 온실을 생각해보자. 이때 향이 섞이지 않게 화분 4개를 놓는 방법은 다음의 두 가지뿐이다. 표에서 O는 화분을 놓은 칸이고, 빈칸은 아무것도 놓지 않은 칸이다.
첫 번째 방법이다.
| 칸 | 1열 | 2열 | 3열 | 4열 |
|---|---|---|---|---|
| 1행 | O | |||
| 2행 | O | |||
| 3행 | O | |||
| 4행 | O |
두 번째 방법이다.
| 칸 | 1열 | 2열 | 3열 | 4열 |
|---|---|---|---|---|
| 1행 | O | |||
| 2행 | O | |||
| 3행 | O | |||
| 4행 | O |
두 방법 모두 어느 두 화분도 행과 열과 대각선을 함께 쓰지 않는다. 따라서 N=4인 경우의 정답은 2다. 한편 N=2나 N=3인 경우에는 어느 칸에 놓아도 향이 섞이는 화분이 생기기 때문에 정답이 0이다.
입출력 예시
예시 1
입력
4
출력
2
예시 2
입력
2
출력
0
예시 3
입력
8
출력
92
입력 조건
가장 먼저 첫째 줄에 온실의 한 변의 칸 수 N이 주어진다. N은 1 이상 13 이하의 자연수다. 입력은 이 한 줄로 끝난다.
온실의 바닥은 N개의 행과 N개의 열로 나뉘어 있으므로 칸은 모두 N×N개이고, 행 번호와 열 번호는 각각 1 이상 N 이하의 자연수다. 놓아야 하는 화분의 개수도 N개로 같다.
출력 조건
향이 하나도 섞이지 않게 화분 N개를 놓는 방법의 수를 첫째 줄에 출력한다. 방법의 수는 0 이상의 정수이며, 놓는 방법이 하나도 없으면 0을 출력한다.
요구사항
- 화분은 정확히 N개를 놓습니다
- 두 화분이 같은 행이나 같은 열, 또는 같은 대각선 위에 있으면 향이 섞입니다
- 화분이 놓인 칸의 모임이 다르면 서로 다른 방법으로 셉니다
- 놓는 방법이 하나도 없으면 0을 출력합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 13개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 13개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 13개를 전부 통과해야 해결입니다.
2
0
4
2
8
92
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.