9646번 - 다이어그램과 태블로 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 349 | 90 | 59 | 32.778% |
문제
영 다이어그램이란 박스를 다음과 같은 조건에 따라서 배열한 것이다.
- 박스는 각각의 행과 열에 대해서 연속적이어야 한다.
- 모든 행은 모두 가장 왼쪽을 기준으로 정렬되어 있어야 한다.
- 각각의 행은 바로 위에 있는 행보다 길 수 없다.
다음은 영 다이어그램의 예시이다.
영 태블로는 영 다이어그램에 아래와 같은 조건을 지키면서 수를 채운 것이다.
- 각각의 박스에는 1과 N을 포함하는 그 사이의 정수가 채워져 있다.
- 각 박스에 적혀있는 정수는 왼쪽에 있는 정수보다 크거나 같아야 한다.
- 각 박스에 적혀있는 정수는 위에 있는 정수보다 커야 한다.
N = 3인 경우 아래 그림은 가능한 영 태블로의 예시이다.
N과 영 다이어그램의 형태가 주어졌을 때, 영 태블로를 만드는 방법의 수를 구하는 프로그램을 작성하시오.
입력
각각의 테스트 케이스는 두 줄로 이루어져 있다. 각 테스트 케이스의 첫째 줄은 영 다이어그램을 나타낸다. 첫 번째로 주어지는 수 k는 1 ≤ k ≤ 7을 나타내며, 행의 개수를 나타낸다. 다음 k개의 정수는 각 행에 있는 박스의 개수 l1, l2, ... , lk이며, 7 ≥ l1 ≥ l2 ≥ ··· ≥ lk ≥ 1을 만족한다. 둘째 줄에는 N이 주어지고, k ≤ N ≤ 7을 만족한다.
출력
각각의 테스트 케이스마다 만들 수 있는 영 태블로의 개수를 출력한다.
예제 입력 1
1 1 1 1 1 2 2 2 1 4 4 3 2 1 1 4
예제 출력 1
1 2 20 20
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2013 D번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호