3160번 - 24 성냥개비 퍼즐 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 18 | 10 | 10 | 58.824% |
문제
24 성냥개비 퍼즐은 혼자서 즐길 수 있는 아주 재미있는 게임이다.
놀이 방법은 아래와 같다.
먼저, 24개의 성냥개비를 아래 그림처럼 놓는다.
+--+--+--+ |..|..|..| |..|..|..| +--+--+--+ |..|..|..| |..|..|..| +--+--+--+ |..|..|..| |..|..|..| +--+--+--+
두 개의 연속된 '-'는 가로로 놓인 성냥개비를, 두 개의 연속된 '|'는 세로로 놓인 성냥개비를 의미한다.
또한, '+' 표시는 성냥개비 두 개 이상의 끝점이 만날 수 있는 위치를 의미하며, '.' 은 빈 공간이다.
이제 위의 그리드에는 총 14개의 정사각형이 있다. (1*1 정사각형 9개, 2*2 정사각형 4개, 3*3 정사각형 1개)
성냥개비를 다 놓은 이후, 적당한 정수 N과 K를 고른다.
이제 아래 조건을 만족하도록 그리드에서 성냥개비를 제거하면 된다.
- 그리드에서 제거하는 성냥개비의 개수는 정확히 N개이다.
- 남은 그리드에서 찾을 수 있는 정사각형의 수는 정확히 K개이다.
- 남아 있는 모든 성냥개비는 최소한 하나의 정사각형을 이루는 데 쓰여야 한다.
재혁이는 지난 1년간 매일 동아리방에서 혼자 성냥개비 퍼즐을 가지고 놀았지만 성냥개비 퍼즐에 성공한 경우가 없었다.
재혁이는 이것이 자신의 실수가 아니라 N과 K의 값을 잘못 골라 퍼즐의 정답이 존재하지 않는 것이 원인이라 생각했다.
남규는 이런 재혁이의 핑계를 깨부수기 위해, N과 K가 주어지면 해당 퍼즐의 정답을 찾아주는 프로그램을 작성하려 한다.
입력
첫 줄에 정수 N과 K가 주어진다. (1 ≤ N < 24, 1 ≤ K < 14)
N은 제거할 성냥개비의 수, K는 남아 있어야 할 정사각형의 수이다.
출력
문제의 조건을 만족하는 그리드를 아래와 같이 출력한다.
- 성냥개비 두 개가 만날 수 있는 모든 점 : '+' (성냥개비가 해당 위치의 상,하,좌,우에 놓이지 않아도 '+'를 출력해야 한다).
- 성냥개비가 놓여 있지 않은 모든 점 : '.'
- 가로로 놓인 성냥개비 : 연속된 두 개의 '-'
- 세로로 놓인 성냥개비 : 연속된 두 개의 '|'
항상 정답이 존재하는 입력만 주어진다.
만약 문제의 조건을 만족하는 그리드가 여러 가지라면, 임의의 하나를 출력한다.
예제 입력 1
20 1
예제 출력 1
+--+..+..+ |..|...... |..|...... +--+..+..+ .......... .......... +..+..+..+ .......... .......... +..+..+..+
예제 입력 2
5 4
예제 출력 2
+--+--+--+ |..|..|..| |..|..|..| +--+--+..+ |.....|..| |.....|..| +--+--+..+ |........| |........| +--+--+--+
예제 입력 3
4 6
예제 출력 3
+--+--+--+ |..|..|..| |..|..|..| +--+--+..+ |..|..|..| |..|..|..| +--+--+..+ |........| |........| +--+--+--+
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Regional Competition - Seniors 4번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호