[백준 / BOJ] 17135 캐슬 디펜스

문제

출처 : https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

N*M배열에 적이있고 N-1번째 줄에 궁수가있다.

 

매 턴마다 궁수는 자기의 사정거리안에서 가장 가까운적(가까운적이 여러명이라면, 가장 왼쪽적)을 찾아 공격하고 궁수의 공격이 끝난후 적은 한칸 아래로 내려온다.

 

궁수는 일제히사격하므로, 한 적에게 여러궁수가 공격할수있다.  

 

이때, 가장많은 적을 없애는 경우의 수를 구하는 문제다.

 

풀이

시뮬레이션 문제였다. 

 

최악의경우 (N=15, M=15)일때 반복횟수를 계산해보자.

 

1. N-1번째 행에 궁수 3명을 놓을수있는 모든 경우의수 = 15C3 = 1850

2. 가장 가까운 적을 찾는 반복횟수 = 3*N*D = 3 * 15 * 15 = 675

3. 매 턴마다 적이 내려오는 시간 = N*M = 225

4. 적을 이미 사격했는지 체크하는 배열을 초기화하는 시간 = N*M = 225

 

위의 과정을 전부 곱하면, 630억정도 나온다.

 

시간초과를 피하기위해, 위의 탐색방법을 적절히 바꿔서 풀어야했다.

1번과 2번은 잘못바꿀경우, 반례가 생길수있기때문에,(가능하다면, 모든경우를 보는것이 가장 확실한 방법이므로) 3번과 4번 과정을 바꾸며 최적화를 시켜줬다.

 

우선, 3번은 다음과 같이 바꿀수있다.

매 턴마다 적이 내려오는 시간 -> 매 턴마다 궁수를 올리는시간 

매 턴마다 적을 한칸씩 내리기위해선, 배열을 복사해가며 적의 위치를 내려줘야한다. 따라서, N*M의 시간이 걸리는데, 위 처럼 궁수를 올리면, O(1)만에 봐줄수있다.

예를들어, 1번째 턴에서 궁수의 위치를 (N+1,1) (N+1,2) (N+1,3) 라고하자. 궁수는 (N~N-D)번째 행의 가장 가까운적들을 사격할것이고, 적들은 한칸 내려오고 성에 도착해 사라진다. 따라서, 궁수는 두번째턴에서 N번째에 있는적을 절대로 사격하지 못한다.

 

4번은 최대 탐색횟수가 1850이므로  3차원 배열을 통해 체크해주며 최적화 시킬수있다.

check[y][x][cnt] = 이미 사격한 적인가?

탐색마다 cnt를 +1해주며 체크한다. 최대 탐색횟수가 1850이므로 cnt의 최댓값은 1850을 넘어가지않는다.

 

이렇게 구현하면 최종 반복횟수는

 

1. N-1번째 행에 궁수 3명을 놓을수있는 모든 경우의수 = 15C3 = 1850

2. 가장 가까운 적을 찾는 반복횟수 = 3*N*D = 3 * 15 * 15 = 675

3. 매 턴마다 적이 내려오는 시간 = N*M = 1

4. 적을 이미 사격했는지 체크하는 배열을 초기화하는 시간 = N*M = 1

 

약 백만번 이다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/17135%20%EC%BA%90%EC%8A%AC%20%EB%94%94%ED%8E%9C%EC%8A%A4/main.cpp

devxb/JJUNalgo