[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
1/7