https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 이번 KOI 고등 1번 난이도>>>>>>>이번 KOI 고등 2번 난이도라고 생각한다. 먼저 모든 정점의 가중치를 x+a나 -x+b로 표현 가능하다. 이를 통해 가중치의 합의 최소 = 절댓값 함수에서의 최솟값을 이용하면 된다. 이때 사이클이 있을때의 예외를 잘 처리해야 하는데, 사이클이 있을 때 어떤 임의의 두 인접한 정점에서 유일한 x값이 나오는 경우가 있다. 이를 주의하..

22348번: 헬기 착륙장 (acmicpc.net) 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net dp[i][j] = i개의 동심원, j개의 빨간 페인트를 이용했을 때 만들 수 있는 동심원 갯수 라고 두면 점화식은 이렇다 dp[i][j] += dp[i-1][j-i] (헤당 동심원에 빨간색 원을 만들 때) dp[i][j] += dp[i-1][j] (헤당 동심원에 파란색 원을 만들 때) 이때 우리는 만들 수 있는 모든 헬기 착륙장의 갯수를 만들어야 하므로, i

https://www.acmicpc.net/problem/1056 1056번: 수 1부터 시작해서 N을 만들려고 한다. 사용할 수 있는 연산은 아래와 같이 총 3가지이다. 이때, N을 만드는데 사용하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오. 현재 수를 1 증가시킴 (현 www.acmicpc.net 누가 봐도 DP를 이용하는 것이다. dp[i] = i를 만드는데의 최소 연산 수 . a^k

BOJ 2487 : 섞기 수열 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 간단한 문제이다. 우리는 이 섞기를 반복하다보면, 어떤 특정한 원소끼리 값이 순환된다는 걸 알 수 있다. 이를 이용하면 답이 LCM(순환하는 그룹들의 순환 주기)라는 걸 알 수 있다. Union-find를 통해 각 순환되는 그룹 원소 갯수(=그룹들의 순환 주기)를 구해주고, LCM을 적용하면 된다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS developme..

BOJ 20984 : Growing Vegetables is Fun 4 20984번: Growing Vegetables is Fun 4 Bitaro likes gardening. He is now growing plants called Biba-herbs in the garden. There are N Biba-herbs in the garden, planted in a line from the west to the east. The Biba-herbs are numbered from 1 to N from the west to the east. Now, the height of the B www.acmicpc.net Prefix-sum을 이용해 풀 수 있다. ldp_i : 1~i번째 배추까지 증가 상태를..

BOJ 11812 : K진 트리 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 트리에서 두 정점간의 거리를 구할때 할 수 있는 방법은 LCA(A,B) = A와 B의 최소 공통 조상 dist(A,B) = A와 B 사이 거리 이라고 할때, dist(A,B) = dist(A, LCA(A,B))+ dist(LCA(A,B), B) 이다. 그러므로 우리는 LCA를 구해 두 정점 간의 거리를 알아내야 하는데, 방법은 나이브로 뚫린다. K진 트리에서 현재 있는 ..