본문 바로가기

BOJ

 (55)
[BOJ 20930] 우주 정거장 https://www.acmicpc.net/problem/20930 20930번: 우주 정거장 첫 번째 줄에는 우주 정거장 개수 $N$과 질문의 개수 $Q$가 주어진다. ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$) 다음 $N$개의 줄에는 $i$번 우주 정거장의 양 끝점을 나타내는 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$ www.acmicpc.net Tag : dsu, greedy 문제요약 이차원 평면 상의 선분이 N개 주어진다. x축 또는 y축과 평행한 방향으로는 마음대로 이동할 수 있을 때 쿼리마다 각 선분을 오갈 수 있는지 구하는 문제다. 풀이 x축으로 한번, y축으로 한번 정렬하고 현재 컴포넌트에서 가장 오른쪽인 점 >= 다음 점의 x 중 ..
[BOJ 22954] 그래프 트리 분할 https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할 첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u www.acmicpc.net Tag : case work, dsu, constructive 문제요약 무향 그래프 \(G(N, M)\)이 주어진다. 간선을 원하는 만큼 삭제해 서로 다른 크기의 트리 2개로 분할하라. 불가능한 경우는 -1을 출력한다. 풀이 새벽에 할 짓이 없어서 tony9402님이 골라온 문제를 풀었다. 일단 일반 ..
[BOJ 20532] 정점 간 통신 네트워크 https://www.acmicpc.net/problem/20532 20532번: 정점 간 통신 네트워크 주식으로 엄청난 돈을 벌어들인 영욱이는 그 돈으로 나라를 세우고 나라의 통신을 담당하는 통신탑을 설치했다. 다들 알다시피 영욱이의 나라는 $N$개의 지역과 이를 잇는 $N-1$개의 도로로 이 www.acmicpc.net Tag : tree dp, number theory 문제요약 조상과 자손 관계인 정점 쌍(x, y) 중 a[x]와 a[y]가 약수와 배수 관계인 것의 개수를 구해라. 풀이 dfs가 어떻게 돌아가는지 잘 알고 있다면 쉽게 풀 수 있다. 자손의 입장에서 조상을 세주도록 하겠다. 일단 루트부터 자신까지의 경로에서 숫자들의 등장 횟수를 구하는 방법은 다음과 같다. 현재 정점의 dfs가 시작되..
[BOJ 20929] 중간 https://www.acmicpc.net/problem/20929 20929번: 중간 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로, 실제 입출력과는 다르다. 위 예시는 $N=2$이고, $A=[1,2]$, $B=[2,3]$인 경우에 대한 입출력이다. www.acmicpc.net Tag : binary search 문제요약 정렬된 배열 a, b를 합쳤을 때 k번째 수를 2logn번 이하의 쿼리로 구해라. 풀이 https://kim1109123.tistory.com/48 위 문제의 시간복잡도가 \(O(logn)\)으로 강제된 문제다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; u..
[BOJ 23719] K번째 음식 찾기 1 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1 한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면 www.acmicpc.net Tag : binary search 문제요약 정렬된 배열 a, b가 입력으로 주어지고 쿼리마다 a[1 : p], b[1 : q]에서 k번째 수를 찾는 문제다. 풀이 2019 한양대학교 sw 특기자 면접 1번, 2021 ioi 계절학교 면접 1번 문제와 같은 문제다. 쿼리당 \(O(log^2n)\)의 풀이를 짜도 돌아는 가지만.... \(O(logn..
[BOJ 9576] 책 나눠주기 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net Tag : greedy 문제요약 각 학생은 [a, b]에 있는 책을 하나씩 고를 수 있다. 책 한권은 한 사람만 고를 수 있다. 이 때 최대 매칭을 구하라. 풀이 이 문제를 처음봤을 땐 티어를 안보고 생각해서 이건 무조건 이분매칭 기본 문제다! 라고 생각했던 기억이 있네요. (http://boj.kr/2563bad26f364ee6aa5c04e9f97845b7 이분매칭 AC 코드) 정해로 돌아와서 생각..
[BOJ 21817] 포항항 https://www.acmicpc.net/problem/23817 23817번: 포항항 첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 www.acmicpc.net Tag : bfs 문제요약 2차원 격자에 시작점, 식당의 위치가 표기되어있다. 식당 중 5개를 골라 방문하는 최단거리를 구하라. 풀이 이 문제 너무한다. 나는 맵에 식당이 5개만 있는 줄 알았지... K = 식당의 개수 일 때 벡터에 K - 5개의 0과 5개의 1을 넣어서 next permutation을 돌리면 방문할 식당 5개가 골라진다. 중복된 원소의 개수 때문에 이는 실제로 \(O(..
[BOJ 1943] 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net Tag : knapsack dp 문제 요약 동전의 가격과 개수가 주어질 때 이를 정확히 반으로 분배할 수 있는지를 물어보는 문제다. 풀이 N * 동전의 합 = 100 * 100000 = \(10^7\) 이라 냅색을 돌릴 생각을 해봐야한다. 평범한 배낭 2 처럼 개수를 ( \(2 ^ n - 1\) + a ) 형태로 저장한 후 냅색을 하면 맞은 사람 1등에 올라갈 수 있겠다는 생각에 싱..

티스토리툴바