분류 전체보기 (78) 썸네일형 리스트형 [USACO] 2018 January Contest (Silver) 풀이 [15589] Lifeguards (Silver)문제 링크: https://www.acmicpc.net/problem/15589문제 설명: $N$ 마리의 소가 1부터 10억 까지의 단위 시간 사이의 임의의 구간을 덮고 있다. 이 소들 중 한 마리를 제거할 때, 여전히 덮혀 있는 구간의 길이를 최대화 하는 문제이다.문제 풀이: $N$의 범위가 10만밖에 되지 않으므로, 사용하는 좌표 역시 20만개를 초과하지 않는다. 따라서 정렬 및 좌표압축 후 스위핑 비슷하게 단 하나의 소만으로 덮혀 있는 구간과 하나 이상의 소로 덮혀 있는 구간의 길이를 prefix sum으로 계산해 주고, 이를 바탕으로 각 소를 한 번씩 제거해주면서 기존에는 덮혀 있었지만 이제 덮혀지지 않는 구간의 길이를 $O(1)$로 계산해 줄 수 .. [BOJ] 10067 수열 나누기 문제 링크: https://www.acmicpc.net/problem/10067 문제 요약음이 아닌 정수 $n$개로 이루어진 수열이 있다. 이 수열을 $k+1$개로 나누어야 하는데, 한 번 나눌 때 마다 새로 나누어진 각 부분의 원소의 합을 곱한 것 만큼의 점수를 얻을 수 있다. 이 때 얻을 수 있는 점수의 최댓값과 그 순서를 구하는 문제이다.$2 \leq n \leq 100,000$, $1 \leq k \leq \min(n-1,200)$ 이다. 풀이 과정 가장 먼저 해야 할 관찰은 어느 순서로 수열을 자르던 간에 최종적으로 얻는 점수에는 변함이 없다는 것이다. 만약 어떤 부분을 2번 잘라 3개의 수열로 나누고, 이 수열의 합을 각각 $S_1$, $S_2$, $S_3$ 이라고 하자. 만약 왼쪽을 먼저 자.. [BOJ] 1693 트리 색칠하기 문제 링크: https://www.acmicpc.net/problem/1693문제 요약$n$개의 정점으로 구성된 트리가 있다. 이 트리를 $1$에서 $n$번까지의 색깔로 칠하는데 $k$번 색깔로 칠하는 데는 $k$만큼의 비용이 든다. 인접한 정점을 같은 색으로 칠하지 않으려고 할 때 최소 비용을 구하는 문제이다.풀이 과정이 문제를 푸는 데 가장 핵심적인 아이디어는, 트리를 색칠하는 데 많아 봐야 $\lg n$개의 색깔만이 필요하다는 것이다. 맨 처음에는 직관적으로 이 성질을 생각했는데, 좀 더 생각해보고 증명을 해 볼 수 있었다. 증명은 아래에!만약 트리를 색칠하는 데 필요한 색깔이 생각보다 적다는 것을 알게 되면, 다음과 같은 동적계획법을 생각해 볼 수 있다. $DP[a][c]=$ $a$번째 정점을 색.. [BOJ] 15977 조화로운 행렬 2018 KOI 고등부 3번이다. 정해는 2d segment tree래서 그렇게 짰는데 사실 set+이분탐색이 훨씬 짧고 깔끔하고 빠르고 메모리 사용량도 적다고 한다. 하여튼 "정해"는 첫째 열 기준으로 정렬한 다음 둘째 열과 셋째 열에서 2d segment tree를 이용해서 pair의 LIS를 구해주면 된다. 메모리 사용량이 문제고 $200000 * (lg200000)^2$ 개만큼 노드 잡았더니 MLE 뜨길래 적당히 줄여서 해봤더니 맞았다. 왜 맞는지 진짜 모르겠는데 실제로 돌리면 같은 노드도 여러번 탐색하고 그래서 최악의 경우에도 노드 개수가 많이 넘어가지는 않는다고 한다. 시간은 5초 제한에 낭낭하게 3.7초 나왔다. (...) 시간복잡도는 $O(n lg n^2)$, 공간복잡도도 마찬가지.다시는 .. [BOJ] 11377 열혈강호 3 이분 매칭이 변형된 형태로 나는 에드몬드-카프 알고리즘을 사용해서 풀었다.k명은 일을 하나씩 더 할 수 있다는 조건이 있기 때문에, source를 bridge 역할을 하는 s1과 s2에 연결한 다음 각각의 용량을 n과 k로 해주었다. 따라서 s1이 모든 사람이 하는 하나의 일, s2가 k명이 할 수 있는 추가 작업을 뜻하게 된다. 그리고 s1과 s2를 모두 사람을 표현하는 정점에 용량 1로 이어주고, 마찬가지로 사람과 일 사이에도 문제에서 주어지는 대로 용량 1인 간선을 연결해주었다. 마지막으로 일과 sink에도 용량을 1로 하여 이어주었다. 이렇게 네트워크 모델링을 하면 성공적으로 AC를 받을 수 있다. 네트워크 플로우 넘 어렵다 ㅠㅠ 1234567891011121314151617181920212223.. NYPC 본선 가요 이 정도 점수로도 본선가는거 보면 예선 치신 대학생 분들과 고3분들이 적지않은듯 함키보드 주면 좋겠다 [BOJ] 7579 앱 나는 사용가능한 최대 cost를 정해두고 0/1 knapsack을 돌리는걸 파라메트릭 서치로 해서 AC를 받았는데 보니까 아무도 이렇게 풀지 않았다 ㅠㅠ 억울해서 소스를 올린다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include using namespace std; int n,m;int arr[105];int cost[105];int cache[105][10005]; int dp(int idx, int remain){ if(idx==(n+1)) return 0; int& ret=cache[idx][remain]; if(ret!=-1) return ret; int ma=dp(id.. [BOJ] 2629 양팔저울 DP 정의는 $DP(i,j)$=i 이하 번호의 추를 사용하여 왼쪽 저울 - 오른쪽 저울의 무게가 j가 되게 할 수 있는가그러면 $DP(i,j)=DP(i+1,j+weight[i]) || DP(i+1,j-weight[i]) || DP(i+1,j)$라는 점화식이 세워짐. 왼쪽에 올리거나, 오른쪽에 올리거나, 아예 올리지 않거나. 간단한 DP problem 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include using namespace std; int f(int x){ return x+60000;} int n,m;int weight[35];int cache[35][120000]; int dp(in.. 이전 1 ··· 4 5 6 7 8 9 10 다음