[Algorithm] 물풍선 제거

[AJ/ 물풍선 제거 문제]

코멘트

: 2번만에 해결할 수 있었다. 솔직히 처음에는 문제 스케일에 압도(?)돼서 이상한 생각을 해서.. 헤맸던 것 같고, 차근차근히 풀어보니까 은근히 쉬운 문제였다. 하지만 코드 길이도 그렇고 확실히 스케일이 있는 문제인 것 같다

문제 분석

정보를 통해 주어진 물풍선을 주어진 바늘의 개수인 K개의 바늘을 사용해서 최대한 많이(연쇄 작용을 일으켜서) 터트린 다음에

• (1) 1차 목표는 k개의 바늘로 최대한 많은 바늘을 터트리는 것(연쇄 작용을 일으켜야함)

그래도 물풍선이 남았을 때 그 때도 최소한의 바늘을 써서(즉, 최대로 많은 연쇄작용을 일으켜서) 남은 물풍선을 터트려야하는데 이 때 남은 물풍선을 터트릴 때 필요한 최소한의 바늘 개수를 구하는 것이 이문제의 목표이다.

• (2) 최종 목표는 남은 물풍선을 터트릴 수 있는 최소한의 바늘 개수를 구하는 것

문제 해결책 강구

• 처음에 했던 '& 근데 생각해보면 유효범위 내에 가장 많은 물풍선을 가진 물풍선을 터트리는게 가장 효율적이지 않을까?' 이 생각에서 나아가서
• 먼저, '주어진 최대 15개의 물풍선을 하나씩 터트려보는거다 BFS로' 예를 들어, 위에서 맨처음 10을 터트려보면 그에 따라 터지는 모든 물풍선을 다 터트리는거다 (BFS로 구현가능)
• 그렇게 첫번쨰 시행에서 15개를 다 터트려본다 불가능한 케이스지만 대략 정말 최악이라도 1500번밖에 안한다(시행). 그렇게 다 터트려본 결과 다터트렸으면 그냥 0을 리턴하면되고 다 안터졌으면 '가장 많이 터트린 케이스를 선택한다'(탐색하면서 최대 터트린 물풍선의 값과, 좌표, 그리고 그때의 터트린 정보 board를 갱신저장하면서 한다)
  예를 들어 위에서는 10이라고 하면 (3,2) 10을 터트린 케이스로 board를 갱신한다
• 그렇게 첫번쨰 시행이 끝났고(k-=1)
  두번째 시행을 위와 똑같은 과정으로 진행한다
  이 때 시행을 하면서 k가 0이되면 그 때부터는 answer += 1 을 시작한다
• 그렇게 계속 시행을 하다가
  물풍선의 개수가 0이 됐을 때 k가 여전히 양수이면 0을 리턴하면되고
  k가 0이면 answer을 리턴하면 된다.

구현 코드

: 너무 길어서 깃헙에 올림
=> 구현 코드 깃헙 링크

마무리

: 문제 스케일이 크면 너무도 자연스럽게(?) 겁을 먹고 하기 싫어지는 현상이 발생하는데.. 다 충분히 풀 수 있는 문제고 스케일이 크면 쪼개면 된다. 그 쪼개는걸 팔로업하는 것이 힘들지만 그래서 잘 기록하면서 푸는 습관이 중요한 것 같다. 스케일이 크니까 수기로 작성하는건 무리가 있고, 컴퓨터를 활용해서 기록하면서 푸는 습관을 들이자.