돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/10067 문제 소개 길이 n의 수열을 k번 자른다. 자를 때 마다, 자른 후 양쪽 수열의 값의 각각의 합을 곱한 것만큼 점수를 얻는다. 이때 얻을 수 있는 최대 점수와 자르는 방법을 구하시오. 문제 풀이 우리는 이 문제를 최종 시점관점에서 보면서 점수에 어떤 값을 이 추가되었는지를 살펴보아야 한다. (a,b,c,d)를 (a,b),(c,d)로 잘랐다고 하자. 이러면 우리는 (a+b)*(c+d)의 점수를 얻게 된다. 이를 다른 식으로 풀어쓰면 ac+ad+bc+bd 만큼의 점수를 얻게 된다는 것이다. 이는 서로 다른 그룹에 속하는 임의의 두 값을 곱해서 더한 값이다. 결국 그전에 어떤 순서로 어떻게 잘랐건 간에, 마지막에 다른 그룹에 있..

문제 태그 : https://www.acmicpc.net/problem/4008 문제 소개 특정 값 a,b,c와 N명의 전투원들의 전투력이 주어진다. 전투원들은 인접한 전투원들끼리 묶어 몇개의 그룹으로 나눌 것이다. 각 그룹의 조정된 전투력은 그 그룹에 속한 모든 전투원의 전투력의 합을 x라고 했을 때, $ax^{2}+bx+c$이다. 이때 가질 수 있는 그룹의 조정된 전투력의 합의 최댓값을 구하시오. 문제 풀이 이 문제를 딱 보자마다 떠오르는 생각은 DP이다. '인접한 것 끼리 묶는다'도 DP를 쓰기 굉장히 좋은 조건이며, 정확히 DP[i]=1부터 i 까지 로 문제를 해결했을 때의 값으로 정의하면 깔끔하게 해결될 것 처럼 보인다. 이를 통해 DP값에 대한 식을 세워보면 다음과 같이 나온다. $DP[i]=..

문제 태그 : https://www.acmicpc.net/problem/13263 문제 소개 나무를 모두 자르고 싶다. 나무 N개의 길이$a_{i}$가 주어지고 N개의 $b_{i}$가 주어진다. 나무 길이 1을 자를때마다 다시 충전을 해야한다. 이때 충전하는 비용은 지금까지 완벽히 자른 나무의 번호 중 가장 큰 번호의 $b_{i}$이다. 이때 $a_{1}=1$ 이고, $b_{N}=0$ 이며, $a_{i}$는 증가하고 $b_{i}$는 감소한다. 문제 풀이 제일 중요한 사실은 $b_{N}=0$이라는 것이다. N번 나무를 자르면 그 이후로는 드는 비용이 0이기 때문에 이 문제를 다르게 해석하면 N번 나무를 자르는데 얼마나 비용이 드는가? 이다. 한 번에 N번 나무를 자를지 중간에 비용을 감소 시킨후 자르는 것..

CHT란? Convex Hull Trick의 약자로 말 그대로 볼록껍질을 이용한 트릭이다. Why? DP 문제에서 왜 사용하게 되는 트릭일까? DP 관계식이 다음과 같이 나왔다고 생각하자. $DP[i]=\underset{j $ax+b$ When? "DP식들을 일차함수꼴로 표현하여 볼록껍질을 만들어 줌으로써 해결을 한다."를 다르게 말해보면, DP식들을 일차함수 꼴로 표현했을 때 볼록껍질이 나오지 않으면 사용할 수 없는 테크닉이라는 것이다. 볼록껍질일 조건은 맨 위의 식에서 $A[j]$의 단조성이다. 주로 최솟값을 뽑을 때에는 $A[j]$가 계속 감소하게 된다. How? 1. 값 구하기 왼쪽과 같이 DP식에 맞는 직선들이 있을때 우리는 연속한 두 직선의 교점을 구함으로써 각 직선이 담당하고 있는 부분을 알..