블로그 언저리인 무언가

문제 : 2110 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 집의 위치와 설치하는 공유기의 개수가 주어졌을 때, 가장 인접한 두 공유기 사이의 거리를 최대로 만들었을 때 그 거리를 출력하는 문제이다. 최적으로 되도록 공유기를 설치했을 때 첫 번째 집에 공유기를 설치하지 않았다면 맨 왼쪽 집의 공유기를 첫 번째로 옮길 수 있으므로 첫 번째 집에 공유기를 설치하는 최적해가 언제나 존재한다. 따라서 첫 번째 집에 공유기를 설치했다고 가정한 후..

문제 : 2020 ICPC Seoul Regional 예선 ICPC Seoul Regional 2020 예선 (ProblemSet / Scoreboard) – ACM-ICPC Korea Regional Site icpckorea.org 어제는 2020 ICPC Seoul Regional 예선을 쳤다. 작년 ICPC가 끝난 이후로 PS공부를 반쯤 때려치운 상태였는데 한 2-3주 남기고 허겁지겁 공부를 다시 하다 보니 확실히 작년에 비해서 코딩 실력이 떨어진 것이 체감되었다. 설상가상으로 원래 팀원이었던 친구가 코로나 19 때문에 2학기를 휴학하고 군대를 가기로 결정해서 급하게 팀원을 구해 참가하게 되었다. 코로나 때문에 덩달아 교내 대회도 취소되어서 친구 자취방에 모여 대회를 진행했다. 이번에도 당연히 등..

문제 : 18116 로봇 조립 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 � www.acmicpc.net 서로 다른 부품이 2개가 주어지고 두 부품이 같은 로봇의 부품이란 것을 알려줄 때, 어떤 로봇의 현재까지 알아낸 부품 개수를 출력하면 되는 문제이다. UnionFind를 사용해 각 부품의 집합을 합쳐주고, 집합을 합칠 때 집합의 크기도 따로 저장해 합쳐주면 된다. Code #include #define ll long long using namespace std; ll N, arr[1000005], cnt[1000005]; ll Fin..

이번에도 좀 디자인적 부분을 수정하고 편의 기능을 추가하기로 했다. 저번에 점수가 바뀔 때 모션이 나오도록 만들었는데 점수가 이동할 때 사용자가 몇 점을 얻는지 알려주지 않으므로 이를 알려주는 부분이 있으면 좋을 것 같아 만들었다. 또 뭘 만들까 곰곰이 생각해보다 현재까지의 점수 변동 기록을 볼 수 있었으면 좋겠다는 생각이 들어서 점수 기록표를 만들기로 했다. 만들다 보니 입력창 내부에서 스크롤을 만드는 법을 몰라 고생했는데 크기가 정해진 것에서만 스크롤이 가능해 입력창 전체를 스크롤하는 게 아니라 그리드를 스크롤해야 한다는 사실을 배웠다. ▶▶▶ 구경하러가기 ◀◀◀

문제 : 13140 Hello World! 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 숫자 N이 주어질 때, hello + world = N을 만족하는 서로 다른 한자리 자연수 d, e, h, l, o, r, w를 출력하는 문제이다. next_permutation을 사용해 모든 경우의 수를 체크해 만족하는 수를 찾아 출력하면 된다. Code #include #define ll long long using namespace std; ll N; vecto..

문제 : 1162 도로포장 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하� www.acmicpc.net 길을 지나는데 걸리는 시간과 포장해서 지나는 시간을 0으로 만들 수 있는 횟수가 주어졌을 때, 최소 시간을 구하는 문제이다. visit배열을 만들 때 1차원이 아니라 2차원으로 만든 후 Dijkstra 알고리즘을 사용해 지금까지 포장한 도로 개수당 최솟값을 구하면 된다. 최소 시간이 최대 10,000,000,000까지 커질 수 있으므로 배열의 초기값을 그보다 더 크게 잡아야 하는 것에 주의하자 Co..

문제 : 1446 지름길 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 고속도로의 길이와 자름길 정보가 주어질때, 운전해야하는 거리의 최솟값을 구하는 문제이다. Dijkstra 알고리즘을 사용해 최단거리를 구하면 된다. Code #include #define ll long long #define INF 1e9+7 using namespace std; struct ABC{ ll idx, dst; ABC() {} ABC(ll idx, ll dst) : idx(idx), dst(dst) {} }; bo..