BOJ (25) 썸네일형 리스트형 [BOJ] 13309 트리 문제 링크: https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 Q개의 줄 각각에는 세 정수 b, c, d가 주어진다. d = 0이면, b와 c를 연결하는 경로가 존재하는 지 묻는 질의만 수행함을 의미한다. d = 1이면, b와 c를 연 www.acmicpc.net 문제 요약: 정점이 20만개인 트리가 주어진다. 이때 어떤 정점 a, b를 잇는 경로가 있는 지에 대한 쿼리 20만개에 응답.. [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] 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.. [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.. [BOJ] 10840 구간 성분 진짜 어이없게 풀었다. 처음에는 해싱인지 모르고 $O(n^3)$에 최적화 생각했는데롤링 해시 구현하기 귀찮아서 그냥 알파벳에 숫자 하나씩 할당해 놓고 다 더한다음에 일치하면 okay라고 판별했다.int 범위 내에서 하니까 충돌나길래 long long 범위까지 늘렸더니 어셉됐다 ㅋㅋㅋㅋㅋㅋ결과적으로는 $O(n^2 lg n) 풀이임. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include using namespace std; typedef long long ll; ll prime[]={1553543355441,683.. 이전 1 2 3 4 다음