문제 96
야채가 싫어요
정환이는 야채를 너무나도 싫어해서, 음식에 야채가 조금이라도 들어있다면 먹지 못하고 버린다.
이를 불쌍히 여긴 서진이는 정환이를 위해 $N\times N$ 크기의 격자판에 음식을 만들어주려 한다.
정환이가 먹을 수 있는 음식은 다음 조건을 모두 만족해야 한다.
- 각 칸은 야채, 고기, 과일, 빈칸 중 하나이다.
- 각 열에는 과일이 정확히 $1$개씩 있다.
- 고기는 과일과 상하좌우로 인접할 수 없다.
- 빈칸의 개수는 $N$개 이하이다.
- 야채가 있는 칸은 존재하지 않는다.
예를 들어, 아래 음식은 세 번째 열에 과일이 $3$개 있으므로 정환이는 이 음식을 먹을 수 없다.
격자판의 크기 $N$이 주어졌을 때, 정환이가 먹을 수 있도록 음식을 만들어 보자.
야채는 V, 고기는 M, 과일은 F, 빈칸은 .로 나타낸다.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100)$
출력
첫 번째 줄부터 $N$개의 줄에 걸쳐 정환이가 먹을 수 있는 음식을 나타내는 $N\times N$ 크기의 격자판을 출력한다. 각 줄에는 격자판의 한 행을 나타내는 $N$개의 문자를 출력한다.
가능한 정답이 여러 개라면 그중 아무거나 출력한다.
예제 입력 1
2
예제 출력 1
F. .F
공식 해설
첫 번째 행을 모두 과일 F로 채운다. 두 번째 행이 있다면 모두 빈칸 .으로 채우고, 세 번째 행부터는 모두 고기 M으로 채운다.
각 열의 과일은 첫 행의 하나뿐이다. 과일의 좌우에는 과일만 있고, 아래에는 빈칸이 있으므로 고기와 인접하지 않는다. 빈칸은 $N\ge2$일 때 정확히 $N$개, $N=1$일 때 $0$개이며 야채는 없다.
따라서 모든 $N$에서 같은 구성법이 성립한다. $N=1$이면 첫 행의 F만, $N=2$이면 과일 행과 빈 행만 출력하면 된다.
출력량이 $N^2$이므로 시간복잡도는 $O(N^2)$이다. 한 행씩 문자열을 만들어 출력하면 추가 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
string(N, 'F')로 첫 행을, $N\ge2$이면 string(N, '.')로 두 번째 행을 출력한다. 남은 행은 string(N, 'M')으로 출력하면 된다. $N=1,2$도 반복문의 범위만으로 처리된다.
C 구현
N+1칸 행 버퍼를 만들고 첫 행은 F, 둘째 행은 '.', 이후 행은 M으로 채운다. 각 행의 끝에 '\0'을 붙여 출력한다. N*N 전체 격자를 저장할 필요는 없다.
Python 구현
'F'*N, '.'*N, 'M'*N을 행 단위로 출력한다. N=1이면 첫 행만 출력하고 N=2이면 뒤의 M 행은 없다. 전체 격자를 리스트에 모을 필요는 없다.
Java 구현
String.repeat(N)으로 행을 만들고 필요한 횟수만 출력한다. Java 21에서 사용할 수 있는 표준 API이며 2차원 배열이나 패턴 생성 클래스를 만들 필요는 없다.
Rust 구현
"F".repeat(N)처럼 한 행만 만들고 BufWriter로 출력한다. 첫·둘째 행을 N 범위 안에서만 출력하고 나머지 M 행을 반복한다. 격자 전체를 메모리에 저장하지 않는다.
JavaScript 구현
문자열의 repeat(n)으로 한 행을 만든다. 첫 행은 F, 두 번째 행이 있으면 ., 그 뒤는 M이다.
const fs = require('node:fs');
fs.writeSync(1, 'F'.repeat(n) + '\n');
if (n >= 2) fs.writeSync(1, '.'.repeat(n) + '\n');
for (let r = 2; r < n; r++)
fs.writeSync(1, 'M'.repeat(n) + '\n');한 행씩 출력하면 전체 격자 배열 없이 $O(N)$의 추가 메모리를 사용한다. $N=1$에서는 F 한 글자만, $N=2$에서는 첫 두 행만 출력하므로 같은 구성에서 경계도 처리된다. 출력 문자를 다른 과일·고기 이름으로 바꾸지 않는다.