1/7

[boj 24101~24105]

*모두 only output 문제로, 문제 특성상 답만 베껴서 제출할 수 있어 코드를 올리지 않았다. 직접 풀어보길 권한다.

- boj 24101 ac, 골2

태그로 dp가 달려 있지만 제한이 작아 손으로 풀 수 있다.

- boj 24102 ac, 플3

가로폭이 좁아 bitDP로 풀 수 있다. 여기까진 UFO가 1칸이라 사실상 뒤에 3문제랑은 결이 다르다.

- boj 24103, 24104 ac, Unrated

너무 커서 dp도 못한다. 그냥 보드를 탐색하며 UFO를 놓을 수 있다면 바로 놓도록 하고, 탐색 시작점을 랜덤으로 바꿔가며 최대한의 해를 찾게 한다. 이후에는 휴리스틱의 한 종류인 유전 알고리즘을 사용했는데, 18789번인 814-2 문제를 풀기 위한 알고리즘으로 접해본 적이 있어 빠르게 생각할 수 있었다. (이것도 이미 웰노운이라고 한다..) 지역 최적점에 놓여 일을 제대로 못하고 있으면 그 부분만 풀어줬고, 아예 다른 방향으로 흘러간다면 갈아엎고 다시 길을 잡아주는 등 베이비시팅을 통해 알고리즘을 어떻게든 끌고 가서 만들었다.

먼저 풀었던 루비, 마스터 분들이 난이도 기여를 하지 않으셔서 Unrated 상태였고, 24103은 다5, 24104는 다4로 기여했다.

- boj 24105