24 성냥개비 퍼즐
시간 제한1초메모리 제한128 MB
N개와 K값이 주어지면 24개 성냥개비로 만든 3x3 격자에서 성냥개비 N개를 제거해 정사각형이 정확히 K개 남고 남은 성냥개비가 모두 어떤 정사각형의 변이 되도록 만듭니다.
문제
24개의 성냥개비로 이루어진 3×3 격자 퍼즐을 생각하자. 처음에는 모든 성냥개비가 다음과 같이 놓여 있다.
+--+--+--+
|..|..|..|
|..|..|..|
+--+--+--+
|..|..|..|
|..|..|..|
+--+--+--+
|..|..|..|
|..|..|..|
+--+--+--+
연속한 두 개의 -는 가로 성냥개비 하나를, 연속한 두 개의 |는 세로 성냥개비 하나를 뜻한다. +는 성냥개비 끝점들이 만날 수 있는 위치이고, .은 빈 공간이다.
처음 격자에는 정사각형이 모두 14개 있다. 크기별로는 1×1 정사각형 9개, 2×2 정사각형 4개, 3×3 정사각형 1개이다.
정수 N과 K가 주어진다. 정확히 N개의 성냥개비를 제거하여 다음 조건을 모두 만족하는 격자를 만들어야 한다.
- 제거한 성냥개비의 개수는 정확히 N개이다.
- 남은 격자에서 완성된 정사각형의 개수는 정확히 K개이다.
- 남아 있는 모든 성냥개비는 적어도 하나의 완성된 정사각형의 변으로 사용되어야 한다.
조건을 만족하는 격자 하나를 출력하는 프로그램을 작성하라.
입력
첫 줄에 정수 N과 K가 주어진다. (1 ≤ N < 24, 1 ≤ K < 14)
N은 제거할 성냥개비의 수이고, K는 남아 있어야 하는 정사각형의 수이다.
출력
조건을 만족하는 격자를 10줄로 출력한다.
- 성냥개비 끝점들이 만날 수 있는 모든 위치에는
+를 출력한다. 그 위치의 위, 아래, 왼쪽, 오른쪽에 성냥개비가 없어도+를 출력해야 한다. - 성냥개비가 놓이지 않은 모든 위치에는
.을 출력한다. - 가로 성냥개비 하나는 연속한 두 개의
-로 출력한다. - 세로 성냥개비 하나는 연속한 두 개의
|로 출력한다.
입력은 항상 조건을 만족하는 답이 존재하도록 주어진다. 가능한 격자가 여러 개라면 아무 것이나 출력해도 된다.