26127번 - 노노그램 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 144 | 55 | 44 | 40.367% |
문제
노노그램은 직사각형 격자를 규칙에 맞게 색칠하는 퍼즐 게임이다. 격자의 각 행과 열에는 양의 정수의 배열이 힌트로 주어지는데, 이는 각 행 또는 열에서 연속한 칠해진 칸의 배열을 나타낸다.
예를 들어 위의 왼쪽 그림을 보자. 4행에 있는 힌트 $[10]$은 해당 행에서 연속한 $10$칸을 색칠해야 함을 나타낸다. 색칠할 $10$칸은 아무 곳에서나 시작해도 되고, 그 외의 칸은 비워 놔야 한다.
이번에는 9행에 있는 힌트 $[3,4,4]$에 주목하자. 이는 해당 행에서 순서대로 $3$칸, $4$칸, $4$칸의 연속한 칸을 색칠해야 함을 나타낸다. 힌트의 순서와 칠해진 칸의 순서는 일치해야 하며, 각 연속한 칠해진 칸 사이에는 하나 이상의 빈 칸이 있어야 한다.
이해를 돕기 위해 위의 오른쪽 그림에는 4행과 9행만 남겨 두었다.
윤이는 노노그램을 풀면서 반드시 색칠해야 하는 칸과 비워 둬야 하는 칸 몇 개를 알아냈지만, 더 이상 진행이 되지 않아 애를 쓰고 있다. 방법을 고민하던 윤이는 문득 어떤 행 하나에 대해서 조건에 맞게 색칠하는 경우의 수가 궁금해졌다. 행의 힌트와 행의 각 칸에 대해 윤이가 알아낸 정보가 주어지면, 해당 행을 조건에 맞게 색칠하는 경우의 수를 구하시오.
입력
첫 번째 줄에 행의 길이 $N$과 힌트 배열의 길이 $K$가 공백으로 구분되어 주어진다. ($1\le K\le N\le 3\ 000$)
두 번째 줄에 힌트를 나타내는 $K$개의 정수가 공백으로 구분되어 주어진다. 각 정수는 $1$ 이상 $N$ 이하이다.
세 번째 줄에 행의 정보를 나타내는 길이 $N$의 문자열이 주어진다. 문자열은 ‘.’, ‘O’, 또는 ‘X’로 이루어져 있으며, ‘.’은 아직 정보를 얻지 못한 빈 칸, ‘O’는 반드시 색칠해야 하는 칸, ‘X’는 반드시 비워 둬야 하는 칸을 나타낸다.
출력
조건에 맞게 행을 색칠하는 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.
예제 입력 1
10 2 2 3 ..X..X..O.
예제 출력 1
4
조건에 맞게 행을 색칠하는 방법을 나열하면 다음과 같다.
OOX..XOOO.OOX..X.OOO..XOOXOOO...XOOX.OOO
예제 입력 2
10 2 2 2 ...OOOO...
예제 출력 2
0
노트
본문에 제공된 노노그램의 출처는 이곳이다. https://www.nonograms.org/nonograms/i/28098
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호