피너클의 it공부방

11280번: 2-SAT - 3https://www.acmicpc.net/problem/11280 SCC를 이용해서 풀었다. (P ∧ ¬Q) ¬P ∨ Q (A ∧ B) 이거는 A and B 이거다.(A ∨ B) 이거는 A or B 이거다.문제는 (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) 이런 식으로 나온다.즉 (A ∨ B) 이게 무조건 True 여야한다. 이제 (A ∨ B) 이걸 (¬A → B) ∧ (¬B → A) 이렇게 바꿔야 한다.그러기 위해서는 먼저 A → B 이게 뭔지를 알아야 한다. A → B 이건 조건문이다. "A 이면 B이다" 이런식으로 가는 것이다.A가 "비가 온다" B가 "우산을 쓴다" 이렇게 가고A가 True고 B가 True면"비가온다" 그러니 "우산을 쓴다" ..

4008번: 특공대https://www.acmicpc.net/problem/4008 dp와 Convex Hull Trick 으로 풀었다. 먼저 dp 식을 만들었다.dp[i] = 0 ~ i까지 특공대를 조직했을때 최대 전투력대충 이정도로 생각해보자. dp[i]를 만들었다고 생각하고 dp[i + 1]로 넘어가자dp[i + 1]은 dp[i]에서 새로운 병사가 추가되어 x[i + 1]이 추가되어야 한다.dp[i + 1] = dp[i] + a * x[i + 1] ^ 2 + b * x[i + 1] + c 하지만 새로 추가될 병사인 x[i + 1]은 앞의 인원과 그룹이 될수도 있다.x[i + 1]과 x[i]이 하나의 특공대가 되게 하려면 dp[i]가 아닌 dp[i - 1]을 사용해야한다.dp[i + 1] = dp[i..

13263번: 나무 자르기Convex Hull Trick 으로 풀었다. 문제를 먼저 봐보자.만약 내가 5번 나무의 높이를 0으로 만들면 5번 보다 번호가 큰 나무를 자르기 전까지는전기톱을 충전할때 b[5]만큼의 비용이 든다. dp[i]는 i번째 나무를 높이가 1이 될때까지 자르는데 필요한 충전 비용의 최소값으로 정의할 것이다.만약에 전기톱을 충전하는 비용이 100이라고 하고 나무의 높이를 10이라고 해보자.우리는 나무를 자르고, 충전한다.높이 10 | 충전 비용 0높이 9 | 충전비용 100높이 8 | 충전비용 200높이 7 | 충전비용 300높이 6 | 충전비용 400높이 5 | 충전비용 500높이 4 | 충전비용 600높이 3 | 충전비용 700높이 2 | 충전비용 800..