문제 백준 2170번 풀이 수직선 상에 테스트 케이스를 나타내봅시다. 현재 선이 그이고 있는가? 그이지 않고 있는가?를 생각해보며 문제를 풀어주면 쉽게 풀 수 있습니다. 선이 그이고 있는가 없는가 는 긋기 시작하면 1을 증가시켜주고, 긋는 것을 멈출 때 1 감소시켜주는 변수 하나로 관리할 수 있습니다. 주석으로 설명을 대체합니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; int main() { io..

문제 백준 1083번 풀이 그리디 문제입니다. $ i $를 $ 1 $부터 $ N $까지 순서대로 순회하면서, $ i $번째에 가능한 수 중 가장 큰 수를 넣어야 합니다. 모든 $ i ( 1 \leq i \leq N) $에 대하여 구간 $ [i, min(i + S, N)] $에 속하는 값 중 최댓값을 $ i $번째에 가져다 놓으면 됩니다. ($ S $는 사용한만큼 감소시킴) $ N $의 범위가 50이므로, 막구현해도 TLE가 나지는 않습니다. 다만, 탐색 범위를 한번 더 확인해서 런타임 에러를 주의할 필요는 있습니다. 소스코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.t..

문제 백준 1226번 풀이 솔직히 문제 번역본이 그렇게 좋은 것 같진 않습니다. $ N $개의 정당 중 $ K $개의 정당을 뽑아서 연합을 만들 수 있습니다. ($ A_{i} $: $ i $번째 정당의 인원수) 이 연합에 속한 정당의 인원들의 합이 전체 정당의 인원수($ \sum_{i=1}^n A_{i} $)의 절반 이상이어야 하며, 연합 중 임의의 한 정당을 뺐을 때 연합의 인원수의 합이 전체 정당의 인원수의 반 미만이 되는 것을 모두 만족해야 합니다. 위 조건을 모두 만족하는 연합 중 가장 많은 인원수를 가지는 연합을 찾는 문제입니다. 문제를 그리디로 접근하면, 정당의 인원수가 많은 것부터 보면서, 전체 정당의 인원수의 절반($ \frac{(\sum_{i=1}^n A_{i})}{2} $)을 처음으로 ..

문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..