A. 문제설명
https://www.acmicpc.net/problem/17135
문제에 대한 자세한 설명은 링크 참조
1. N*M 크기의 땅이 주어짐
2. 각 배열 안에는 적들이 위치하여 한턴마다 아래로 내려옴
3. 궁수 3명이 N+1번째 행에 위치하여 성을 지킴
3. 궁수들은 주어진 사정범위 D안에 들어온 적 중, 가장 가까운 적, 만약 가장 가까운 적이 여럿이라면 그 중에 가장 좌측의 적을 공격
4. 매 턴마다 적들이 내려오고 궁수들은 적을 공격하며 배열내 적들이 모두 내려올 때까지 반복
5. 궁수들이 위치하는 경우 중 최대로 적을 많이 죽일 수 있는 수를 구하라
B. 접근법
DFS + 시뮬레이션
우선, 궁수들이 성벽에 배치되는 경우에 대해서 중복되지 않도록 DFS로 모든 경우를 구해준다.
그리고, 매 턴마다 궁수가 적을 공격하고 적이 한칸씩 내려오며 모든 적이 배열에서 없어질 때까지 반복하는 시뮬레이션을 수행한다.
C. 풀이
1. 궁수들이 벽에 배치되는 조합을 DFS로 구함; 1이 궁수 0이 빈자리로 길이 M의 스트링 조합
2. 해당 조합의 스트링으로 성지키기 시뮬레이션 수행
3. 각각의 궁수는 동시에 적 하나를 공격
3-1. 적들의 위치를 담은 eVec을 생성, 각각의 궁수별로 위치를 계산하여 넣어줌
3-2. 계산된 적 벡터를 궁수와의 거리기준으로, 거리가 같으면 좌측 우선으로 정렬
3-3. 가장 가까운 위치에 있는 적 벡터의 첫번째 원소를 toKill에 저장하여 다음 판부터 제외
* 여기서 궁수의 사정거리 D안에 못드는 적은 죽이지 못하므로 제외
4. 공격받은 적은 게임에서 제외
5. 궁수의 공격이 끝나면, 적이 이동
6. 모든 적이 격자판에서 제외되고 죽인 적이 계수되면 maxKill에 최대값을 업데이트
D. 내 코드
* 풀이를 완료한 후 코드 제출시 런타임 에러가 계속 발생하여 오랜시간 디버깅을 하게 되었다. 결국에 코드내 문제를 찾게 되었을 때, 83번째 라인의 eVec[j].front() 코드 부분에서 eVec[j] 벡터가 빈 오브젝트인 케이스에서 front() 함수를 호출하는 부분에서 런타임 에러가 발생했다는 것을 알게되었다.
cplusplus reference의 설명과 같이, vector::begin 함수와는 다르게, front() 함수는 직접 레퍼런스를 전달한다. 즉, 빈 컨테이너에서 이 함수를 부르는 행동은 undefined behavior가 되는 것이다.
후에, 이 문제를 발견하고는 !eVec[j].empty() 조건을 추가하여 검사하는 것으로 해결하였다.
