백준 4008 특공대 썸네일형 리스트형 [APIO 2010] 특공대 (Commando) 풀이 https://www.acmicpc.net/problem/4008 4008번: 특공대 입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2, www.acmicpc.net Convex Hull Trick (CHT) 를 이용하는 대표 문제로써 2010년 출제 당시 학생들에게 충공깽을 선사했지만 지금은 국민문제가 되어버린 비운의 문제다. 우선 간단한 O(n3)O(n3), O(n2)O(n2) 해법을 간단히 소개하고 그 뒤 CHT 를 이용한 O(N)O(N) 해법을 소개하도록 하겠다. 1. O(N3)O(N3) 해법 간단한 다이나믹 프로그래밍으로 해결 가능하다. D.. 더보기 이전 1 다음
