CS/ProblemSolving
-
7 - 2. 행사 준비CS/ProblemSolving 2023. 9. 23. 15:03
https://www.acmicpc.net/problem/30022 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 그리디 문제중에 기본적이면서도 알면 좋을만한 기법을 쓸 수 있는 문제입니다. 행사 준비하는데 물품 N개가 필요하고, 이를 휴먼1이 A개 휴먼2가 B개를 준비하기로 합니다. 이때 상점 2개가 존재하는데, 각 상점은 물품 x, y, ...에 대해 서로 다른 가격으로 판매하고 있습니다. 이럴땐 담합 좀 하면 ..
-
4 - 3. Xayahh-Rakann at Moloco (Hard)CS/ProblemSolving 2023. 3. 11. 18:25
https://www.acmicpc.net/problem/15509 15509번: Xayahh-Rakann at Moloco (Hard)The first line contains three integers n, m, and k where 1 ≤ n, k, ≤ 1,000 and 1 ≤ m ≤ 1,000,000. The following m lines contain two integers per line where each line describes an inseparable pair of jars (the two integers in the same line are dwww.acmicpc.net 서로소 집합을 만드는 문제입니다. 영문으로 써져있어서 풀기가 너무 귀찮은데, 전 이 정도로 물러날 코더가 아니죠..
-
4 - 2. Closing the Farm (Gold)CS/ProblemSolving 2022. 6. 5. 15:17
https://www.acmicpc.net/problem/12012 12012번: Closing the Farm (Gold) The output consists of
-
7 - 1. 우체국CS/ProblemSolving 2022. 3. 6. 16:19
https://acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 최근에 푼 그리디 문제 중에, 코테에서도 종종 봤던 유형인 것 같아 이번 기회에 기억에 남길겸 정리해보려 합니다. 문제는 읽기 귀찮으니까 대충 그림으로 표현해서 보겠습니다. 아래와 같이 수직선 상 X 좌표에 마을이 존재하고, 각 마을에는 A명의 사람들이 살고 있습니다. 각 사람들의 거리의 합이 최소가 되는 위치에 우체국을 ..
-
1 - 3. 공유기 설치CS/ProblemSolving 2022. 1. 18. 22:41
백준 2110번: 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 사실 이 문제는 푼지 좀 오래 되었는데, 완전 같은 문제를 최근에 풀어서 공유합니다. 문제는 대충보자면, 한정된 공유기 개수를 가지고 많은 집에서 사용할 수 있도록 적절한 위치에 놓고싶다~ 입니다. 문제에 나오는 도현이는 상당히 선한 사람이면서도, 개발자다운 면모를 갖고 있는 듯 하네요. 멋있습니다. 멋있는 도현이를 위해서 저희가 대신 고민해 주도록해요. 물론 저 같이 실력은 조잡..
-
9 - 1. Dijkstra 예제 (Parity Constraint Shortest Path)CS/ProblemSolving 2021. 2. 1. 18:55
백준 20128번: Parity Constraint Shortest Path 20128번: Parity Constraint Shortest Path 첫째 줄부터 N개의 줄에 걸쳐, i번째 줄에 1번 정점에서 i번 정점으로 이동하는 최소의 홀수 경로의 비용과, 최소의 짝수 경로의 비용을 공백으로 구분하여 출력한다. 해당 경로가 존재하지 않는 www.acmicpc.net 풀고 나면 꽤나 쉬운 문제인데.. 방법을 적용하기 위해 증명을 생각하기 조금 어려웠던 문제입니다. 제목을 대충 해석하면 뭔 최단 경로입니다. ㅎㅎ 대략적인 문제 내용을 요약하자면 아래와 같습니다. 1번부터 N번까지 모든 노드의 최단 경로를 구하는 문제입니다. 임의의 두 노드 사이에 존재하는 간선은 단 하나 양방향 노드로 구성되며, 노드수: ..
-
10 - 1. Prefix Sum 예제 (11660: 구간 합 구하기 5)CS/ProblemSolving 2021. 1. 28. 19:21
백준 11660번: 구간 합 구하기5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간 합 구하기, 제목만 봐도 Prefix Sum을 사용해야 할 것 같은 문제입니다. 아닌 경우도 있습니다. ㅎㅎ 그 중에서도 2차원 Prefix Sum 문제 입니다. 왜 Prefix로 풀어야하는 지는 아래와 같습니다. N은 최대 1024, M인 쿼리문은 최대 10만개까지 들어옵니다. 무식하고 돌리면 O (N * N * M) = 약 1000억, 따라서.. 일반 반복문으로 풀긴 어렵겠죠..
-
5. Sparse Table 예제 (18783번: Swapity Swapity Swap)CS/ProblemSolving 2020. 8. 25. 17:59
백준 18783번: Swapity Swapity Swap 18783번: Swapity Swapity Swap Initially, the order of the cows is $[1,2,3,4,5,6,7]$ from left to right. After the first step of the process, the order is $[1,5,4,3,2,6,7]$. After the second step of the process, the order is $[1,5,7,6,2,3,4]$. Repeating both steps a second time yields t www.acmicpc.net LCA 문제를 풀어볼까 했는데, 그보다 풀어보신분들은 아시겠지만, Sparse Table의 개념과 적용에 대한 것이..