분류 전체보기 (29) 썸네일형 리스트형 2021년 정올 본선 2번 그래프 균형 맞추기 루트의 가중치를 미리 0으로 정해둔다고 생각해보자. 그러면 루트와 이어진 정점들은 간선과 같은 가중치를 가지게 되고 그와 이어진 정점들도 간선 가중치 - 이전 정점 가중치가 부여되게 된다. 따라서 모든 정점들은 루트에 의해 가중치가 고정되고 이는 dfs 한번에 구할 수 있다.좀더 자세히 살펴보면 루트로부터의 거리가 홀수면 루트의 가중치가 늘어남에 따라 같이 늘어나고 짝수면 반대로 줄어들게 된다.절댓값의 합을 구하기 때문에 루트의 값이 너무 커지거나 작아지면 최솟값을 구할 수 없고 따라서 그 사이를 삼분탐색으로 구할수 있을 거라는 생각을 했다. 처음에는 트리로 문제를 잘못봐서 삼분탐색만 생각했는데 사이클이 있을 수 있었다.앞서말한 거리에 따라 정점들을 증가와 감소로 경우를 나누어 생각하면 처음 dfs를 돌.. 2021년 정올 본선 1번 헬기 착륙장 최대 반지름이 n인 원을 그리려면 페인트의 색깔과 관계없이 고정적으로 1부터 n까지의 합((n + 1)n / 2)만큼이 필요하다.따라서 dp[i][j] = 최대 반지름이 i인 원을 빨강 페인트 j통을 사용해서 색칠하는 경우의 수로 두었고 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i](가장 바깥 원을 어떤 색으로 칠할지를 나누어서) 가 나오게 된다. 이 DP를 전처리 해 두고 테스트 케이스에서 가능한 원의 크기마다 빨강 페인트의 사용 가능 범위인 max(0, 총 페인트량 - b)(파랑 페인트를 최대로 사용) 부터 a + 1(빨강 페인트를 최대로 사용) 이 나오니 이를 누적합으로 만들어서 해결하였다. 1시 57분 32초 제출, 64점#include #include #includ.. 백준 8872번 빌라봉 https://www.acmicpc.net/problem/8872 8872번: 빌라봉첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. 1 ≤ N ≤ 100,000 0 ≤ M ≤ N-1 0 ≤ A[i], B[i] ≤ N-1 1 ≤ T[i] ≤ 10,000 1 ≤ L ≤ 10,000www.acmicpc.net 일단 각각의 연결된 빌라봉들이 트리형태이니 연결된 빌라봉들마다 한번씩 dfs를 돌려야 할 것 같다.그리고 그 트리가 다른 트리들과 연결될때는 하나의 노드에서만 연결되고 트리에서 그 노드로부터 가장 먼 정점의 거리가 가장 짧게되는 정점을 잡으면 된다.이때 트리마다 나오는 이 거리들을 그 트리의 가중치로 두면 각 트리를 정점으로 하는 큰 트리가 만들어 .. 백준 3015번 오아시스 재결합 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람www.acmicpc.net스택에 어떤 사람의 키와 키가 그 사람 이상이면 볼 수 있는 사람들의 수를 저장해 둔다.그리고 그 사람이 볼 수 있는 사람들은 그 사람을 보는 다른 사람들도 볼 수 있으니 수만 세고 스택에서 제거 한다. #include #include #include#includeusing namespace std;int main(){ ios_base::sync_with_stdio(false);.. 백준 16894번 약수 게임 https://www.acmicpc.net/problem/16894 16894번: 약수 게임구사과와 큐브러버는 약수 게임을 하려고 한다. 약수 게임은 종이에 정수를 적으면서 진행하고, 두 사람은 턴을 번갈아 가진다. 가장 처음에 종이에는 정수 N이 적혀있다. 각자의 턴이 돌아올www.acmicpc.net1 또는 소수가 주어지면 그 즉시 구사과가 이긴다.주어진 수가 두 소수의 곱일때 그 수를 a * b(a, b는 소수)라 할 수 있고 이때 구사과는 수를 a 또는 b로 만들어야 하니 큐브러버가 이기게 된다.위의 경우가 아닐 경우에는 주어진 수는 적어도 3개 이상의 소수의 곱이고 구사과가 두 소수의 곱으로 이루어진 수를 남겨 두번째 경우와 같은 이유로 이기게 된다.따라서 주어진 수가 몇개의 소수의 곱으로 이루.. 백준 11404번 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가www.acmicpc.netdire[a][b]는 a번 노드에서 b번 노드로 가는 비용을 담아둔다.i, j, N을 차례로 반복문에 돌려서 j에서 i를 거쳐 N으로 가는 최단경로를 갱신해준다. #include#includeusing namespace std;int dire[100][100];//초기에 정점간의 거리들을 초기화 해줄 수const int INF = 987654321;int main() { ios_base::sync_wi.. 2019년에 찍은 사진들 사용했던 카메라는 니콘 fm2로 기억합니다. 백준 1967번 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net트리디피와 그리디로 각각 문제를 풀었다. 트리DP 풀이트리의 지름은 지름이 지나는 가장 깊이가 낮은 노드를 루트로 하는 서브트리에 포함된다.이때 해당 노드를 한 끝점으로 하는 경우와 노드를 지나면서 자식 노드들 중 둘을 지나는 경우로 나눌 수 있다. dp[a]를 a번 노드를 루트로 하면서 자식 노드들 중 하나만을 지나는 경로의 길이로 하였고 모든 노드에 대해 최대 두개의 자식 노드.. 이전 1 2 3 4 다음
