백준 17135번 캐슬 디펜스 풀이/해설/코드 (파이썬) 삼성 A형 기출

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

문제 설명을 하고싶은데 문제 설명이 참.. 그림이 있으면 쉬운데 글로 하기가 어렵다. 대충 해보지뭐

 

1. 1과 0으로 구성된 격자가 주어지고 그 격자의 행,열의 길이 그리고 d가 주어진다. 여기서 1을 없애야하는데..

2. 저 격자 맨 아랫쪽의 바깥부분에는 성castle이 있음. 그리고 그 행에서 3부분을 미리 지정해두고, 각 부분에서 해밀턴거리 d인 부분까지의 1을 없앨 수 있다.

3. 1을 없애는 규칙은 총 세가지인데, 첫째는 가까운 것부터 지우기 둘째는 같은 거리에 여러개 있으면 왼쪽부터 지우기 셋째는 성의 각 부분에서 지우는 1은 중복될 수 있다. 가령 한번에 최대 3을 지울 수 있다고 해도 규칙 상 한번에 1개만 지워지는 경우가 생길 수도 있음.

4. 한차례 지우고 나면 그 다음차례에는 격자의 행들이 한칸씩 내려온다.

 

그리고 내가 푼 방식은 이러함.

 

1. itertools로 조합미리 만들기

2. 각 조합마다 행의 갯수 회 동안(한 턴 할 때마다 격자가 한칸씩 내려오므로) 우선순위에 따라 지울 수 있는 인덱스를 확인하면서 그 인덱스에 1이 있으면 표시해둔다.

3. 표시한 인덱스를 0으로 바꾸고 반복.

 

어려운 문제는 아닌데 문자열 인덱스 처리하는게 조금 헷갈려서 거기서 한 10분 까먹고 규칙세번째꺼(지우는 1이 중복될 수 있는거)에서 한 30분 까먹어서 한시간정도 걸려서 풀었다. 세번째 꺼 규칙 조건을 추가했을 땐 바로 풀릴거라고 예상했는데 의외로 또 안되서;; 조금 헤맸다. 근데 알고보니 그냥 내가 조건을 좀 이상하게 넣음.. 근데 또 나는 규칙도 추가한거니까 대체 뭐가문제지?하면서 하나하나 확인해보느라 시간을 박살냈다.

 

아무튼 이것도 시간 오래걸리긴 했어도 혼자 풀어서 기분이 좋다.

 

☆ 앞으로 조건 잘 보고 + 수정할때는 확실하게 수정된건지 확인하기 ★