백준 문제 해설66 백준 25380 커다란 도시 KOI 2022 중등부 1차 2번 문제이다. https://www.acmicpc.net/problem/25380 25380번: 커다란 도시 KOI시는 너무나 커다라서, 이동하려면 시간이 오래 걸린다. 그래서 KOI시는 도시를 관통하는 아주 긴 도로를 건설하였다. 도로는 남북 방향 또는 동서 방향으로 무한히 뻗어 나간다. 남북 방향의 www.acmicpc.net 풀이 섭테별로 의미하는 바가 다르다. 공식해설을 많이 참고한 풀이이다. 이분탐색을 사용하라는 부분은 도저히 이해가 안되더라 그냥 새로 생각해서 풀었다. 시간 복잡도 : $O({N}\log{N})$ 감상 : 드디어 정올 1차 붙었다. 너무 기쁘다. 조만간 후기 하나 올려야겠다. #include #define ff first #define ss sec.. 2023. 5. 15. 백준 20649 Stuck in a Rut 힘내자 https://www.acmicpc.net/problem/20649 20649번: Stuck in a Rut Farmer John has recently expanded the size of his farm, so from the perspective of his cows it is effectively now infinite in size! The cows think of the grazing area of the farm as an infinite 2D grid of square "cells", each filled with delicious grass (t www.acmicpc.net 풀이 ecow, ncow를 구분해주고 사건 정리 및 정렬 후 처리를 진행해준다. /* basic setup .. 2022. 11. 28. 백준 18320 Loan Repayment 훈련을 지배하라 https://www.acmicpc.net/problem/18320 18320번: Loan Repayment Farmer John owes Bessie $N$ gallons of milk ($1\le N\le 10^{12}$). He has to give her the milk within $K$ days. However, he doesn't want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bess www.acmicpc.net 풀이 매개변수 이분 탐색을 통한 풀이이다. 동일한 y에 대한 연산을 한 번에 진행해준다. 이 문제의.. 2022. 11. 27. 백준 4435 중간계 전쟁 1일 1블로그 https://www.acmicpc.net/problem/4435 4435번: 중간계 전쟁 첫째 줄에 전투의 개수 T가 주어진다. 각 전투는 두 줄로 이루어져 있다. 첫째 줄에 간달프 군대에 참여한 종족의 수가 주어진다. 이 값은 공백으로 구분되어 있으며, 호빗, 인간, 엘프, 드워프, www.acmicpc.net 풀이 문제에서 제시된 조건에 맞추어 weighted sum을 구해 비교해주면 되는 문제이다 시간 복잡도 : $O(T)$ 감상 : 오늘의 아티스틱 스위밍 대회 즐거웠다. /* basic setup {{{ */ #include #define ff first #define ss second #define pb push_back #define sz(x) ((int)x.size()) #d.. 2022. 11. 26. 백준 2493 탑 내일 아티스틱 스위밍 대회한다. 많이 기대된다. https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 stack을 사용해 해결해줄 수 있는 문제이다. 특정 위치에 있어서 해당 위치 이전에 있는 탑들이 현재 위치에 있는 탑들보다 작을 경우 이후의 탑들에서 해당 작은 탑들에 도달할 수 있는 방법은 없다. 이 원리를 이용해 한번 탐색해준 탑은 사용하거나 제거해줄 수 있는 것이다. (시간 복잡도 $O(N)$) 감상 이제 이런 문제들은 쉽게 풀린다. .. 2022. 11. 25. 이전 1 2 3 4 ··· 14 다음
