3666번 - 리스크 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 398 | 158 | 116 | 36.364% |
문제
리스크는 세계를 무대로 한 보드 위에서 진행되는 유명한 보드 게임이다. 이 세계는 국경선으로 나뉘어진 여러 지역으로 이루어져 있고, 각각의 지역은 하나의 플레이어에게 배정된다. 모든 지역엔 각 지역을 가진 플레이어의 군대가 하나 이상 주둔해야 한다.
각 턴마다, 당신은 당신의 군대를 제자리에 두거나 인접한 자신의 영토로 보낼 수 있다. 딱히 이동할 군대가 없다면 턴을 패스하는 것도 가능하다. 각 군대는 현재 턴에 주둔한 영역에서 인접한 영역으로의 이동만이 가능하며, 이와 같은 조건 하에서라면 여러 번 군대를 이동시켜도 상관없다. 필요하다면 나누어 보낼 수도 있지만, 모든 군대를 이동시켜 영토에 주둔하는 군대가 0이 되게 할 수는 없다.
일반적으로는 적의 영토와 인접한 영역에 최대한의 군대를 보내는 전략을 사용한다. 이번 턴에 당신은 당신이 가진 영역 중 가장 취약한 영역(즉, 적국과 인접해 있으며 아군의 수가 가장 적은 영역)을 최대한 강하게 만드려고 한다. 이때, 이번 턴이 끝나면 당신의 가장 취약한 영역에 최대 몇 명의 군대가 주둔할 수 있을까?
입력
첫 줄에 테스트 케이스의 수가 주어진다. 이 수는 100을 넘지 않는다.
각 테스트 케이스는 다음과 같이 구성되어 있다.
- 정수 n ( 1 ≤ n ≤ 100 ) : 영토의 총 수
- n개의 정수 ai ( 0 ≤ ai ≤ 100 ) : 각 지역에 주둔하고 있는 당신의 군대 수. 만일 이 값이 0이라면 적군에 의해 점령된 지역임을 의미한다.
- n개의 줄에 걸쳐 n개의 문자 'Y' 또는 'N' : i행 j열의 문자는 i번째 영토와 j번째 영토의 인접 여부를 나타낸다. 'Y' 일 경우 인접하며, 'N' 일 경우 인접하지 않는다. 항상 대칭으로 주어지며, i번째 행의 i번째 열은 항상 'N' 이다.
모든 테스트 케이스에서 당신은 적어도 하나의 영토를 갖고 있으며, 당신의 적 또한 최소한 하나의 영토를 갖고 있다. 또한, 최소한 적국과 하나의 영토는 서로 인접해 있다.
출력
각 테스트 케이스마다 첫 줄에 가장 취약한 영역에 배치될 수 있는 최대의 군대 수를 출력한다.
예제 입력 1
2 3 1 1 0 NYN YNY NYN 7 7 3 3 2 0 0 5 NYNNNNN YNYYNNN NYNYYNN NYYNYNN NNYYNNN NNNNNNY NNNNNYN
예제 출력 1
1 4
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 F번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호