돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/4008 문제 소개 특정 값 a,b,c와 N명의 전투원들의 전투력이 주어진다. 전투원들은 인접한 전투원들끼리 묶어 몇개의 그룹으로 나눌 것이다. 각 그룹의 조정된 전투력은 그 그룹에 속한 모든 전투원의 전투력의 합을 x라고 했을 때, $ax^{2}+bx+c$이다. 이때 가질 수 있는 그룹의 조정된 전투력의 합의 최댓값을 구하시오. 문제 풀이 이 문제를 딱 보자마다 떠오르는 생각은 DP이다. '인접한 것 끼리 묶는다'도 DP를 쓰기 굉장히 좋은 조건이며, 정확히 DP[i]=1부터 i 까지 로 문제를 해결했을 때의 값으로 정의하면 깔끔하게 해결될 것 처럼 보인다. 이를 통해 DP값에 대한 식을 세워보면 다음과 같이 나온다. $DP[i]=..

문제 태그 : https://www.acmicpc.net/problem/13263 문제 소개 나무를 모두 자르고 싶다. 나무 N개의 길이$a_{i}$가 주어지고 N개의 $b_{i}$가 주어진다. 나무 길이 1을 자를때마다 다시 충전을 해야한다. 이때 충전하는 비용은 지금까지 완벽히 자른 나무의 번호 중 가장 큰 번호의 $b_{i}$이다. 이때 $a_{1}=1$ 이고, $b_{N}=0$ 이며, $a_{i}$는 증가하고 $b_{i}$는 감소한다. 문제 풀이 제일 중요한 사실은 $b_{N}=0$이라는 것이다. N번 나무를 자르면 그 이후로는 드는 비용이 0이기 때문에 이 문제를 다르게 해석하면 N번 나무를 자르는데 얼마나 비용이 드는가? 이다. 한 번에 N번 나무를 자를지 중간에 비용을 감소 시킨후 자르는 것..

문제 태그 : https://www.acmicpc.net/problem/17940 문제 소개 출발지에서 목적지까지 지하철을 타고 이동한다. 각 지하철역은 A회사 또는 B회사의 소유인데 방문하는 지하철역의 변경횟수를 최소화 하면서 이동을 해야한다. 만약 횟수가 최소인 경로가 여러가지가 있으면, 경로의 길이가 가장 짧은 경로를 선택한다. 이때 최소 변경횟수와 경로의 길이를 출력하라. 문제 풀이 사전지식 + 간단한 아이디어 하나로 바로 해결할 수 있다. 1. 일단 경로를 구하는것이고 시작점->도착점 하나이기 때문에 기본문제면 다익스트라를 이용해 해결 할 수 있다. 2. 결국 중요한 것은 지하철역 회사가 바뀌는 경로이다. 3. 똑같은 위치로 이동할 때 다른 경로를 아무리 길게 해도 회사가 바뀌는 경로로 가는 것..

문제 태그 : https://www.acmicpc.net/problem/13925 문제 소개 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y) x y v: Ai = v를 수행한다. (x ≤ i ≤ y) x y: (ΣAi) % MOD를 출력한다. (x ≤ i ≤ y) 의 4가지 쿼리를 처리해야하는 문제이다. 문제 풀이 일단 이런식으로 처리하는데에 있어 기본적으로 lazy segment tree를 생각할 수 있다. 하지만 여기서 lazy하게 처리하는 과정에서 걸리는 부분이 있다. 기존의 lazy 방식은 최대한 미루고 나중에 처리해 주는 방식이다. 따라서 한 노드에 처리해 주어야 할 양이 쌓이기도..

797이 들어간 문제로 ICPC 2019 Seoul G번인 이 문제를 선택했다. 문제 태그 : https://www.acmicpc.net/problem/17974 문제 소개 점 N개의 좌표와 색깔이 주어진다. 우리는 이 점들중 1개이상, 몇 개의 점들을 뽑아야 한다. 뽑힌 점들을 A그룹이라고 하자. 뽑히지 않은 점들을 B그룹이라고 하자. 이때 모든 B 그룹의 점들은 가장 가까운 A그룹의 점들에 색깔이 같은 점이 존재해야 한다. 이때 뽑을 수 있는 A그룹의 최소 크기를 구하시오. 문제 풀이 일단 수직선상에 점을 흩뿌려놓고 생각을 해보자. 가장 먼저 연속된 같은 색깔의 점들을 그룹으로 묶어야 한다. 이때 관찰을 할 수 있다. 한 그룹내에서 최소 1개이상의 점은 뽑아야한다. 한 그룹내에서 최대 2개의 점까지만..

어느새 백준 800문제를 앞두게 되었다. 790문제인 상태에서 갑자기 800을 특별하게 찍고 싶어서 791~800은 그 숫자가 문제 번호에 포함된 문제들로 풀기로 하였다. 그 시작은 791이 들어있는 7791이다. 문제 태그 : https://www.acmicpc.net/problem/7791 문제 설명 : 1부터 n까지 n명의 여자와 1부터 2n-1번까지 2n-1명의 남자가 있다. 각 여자 i번은 1번~2i-1번까지의 남자들과만 서로 안다. 이때 서로 아는 K쌍을 고를 수 있는 경우의 수를 구하시오. 문제 풀이 : 뭔가 DP보다는 조합식이나 그런것으로 깔끔하게 떨어질 것 같았다. 하지만 큰 경우에 대해서 값을 구하는 과정도 어려웠고, 적은 양의 표본으로는 규칙을 알 수 없어 아예 모든 경우의 수를 구할..

문제 태그 : https://www.acmicpc.net/problem/10903 문제 소개 원의 갯수와, 원의 반지름과 각 원의 중심의 위치가 주어진다. (모든 원은 반지름이 같다.) 이때 모든 원을 포함하는 도형의 최소 둘레를 구하시오. 문제 풀이 이 문제를 보자마다 딱 이러한 형태의 그림이 떠올랐다. 그림을 보면 알겠지만, 바깥의 전체 둘레의 길이는 원하나의 둘레+ 점 들 사이의 거리의 합이다. 이 그림을 고려하며 문제를 다시 보면, 볼록껍질을 이루는 점들의 이웃한 거리의 합 + 원 하나의 둘레가 정답이 된다는 것을 알 수 있다. 볼록껍질을 잡는 것은 이 글을 통해서 배울 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

문제 태그 : https://www.acmicpc.net/problem/2162 문제 소개 만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제 문제 풀이 선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제. 출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다. 선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

문제 태그 : https://www.acmicpc.net/problem/15647 문제 소개 간선의 가중치가 있는 트리가 주어진다. 1번 노드 부터 N번 노드까지 각 노드에 대해서 다른 모든 노드에서 그 노드까지의 거리의 합을 출력하시오. 문제 풀이 처음에는 하나당 O(logN)에 구하는 방법을 생각했다. HLD나 centriod decomposition을 떠올렸지만, 잘 모르는 쪽이기 때문에 더 이상 풀이를 떠올릴 수 없었다. 분명히 centriod를 활용해 풀 수 있을 것 같긴하다. 그래서 전체를 O(N)으로 구하는 방식으로 바꾸었다. Tree DP를 이용하는 방식이다. F[i] = 내 서브트리의 노드들이 i번 노드까지 오는데 걸리는 거리의 합 cnt[i] = 내 버스트리의 노드 수 dp[i] = 내..

BUSACO 2017 February Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 소가 길을 건너는 이유 시리즈 이고, 한글 번역이 되어있으므로 따로 문제 설명은 하지 않으려 한다. 백준에서는 https://www.acmicpc.net/category/396 에서 볼 수 있다. Bronze 1 문제 설명 : https://www.acmicpc.net/problem/14467 문제 풀이 : 배열에 최근 위치를 저장해서 현재 받은 입력이 최근 위치와 달랐는지 판별하고 횟수를 세준다. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace..