블로그 언저리인 무언가

문제 : 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..

문제 : 1766 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 각 문제를 푸는 시간과 선행 문제가 주어졌을 때, 문제집에서 문제를 푸는 순서를 출력하는 문제이다. 위상 정렬을 사용하지만 가능하면 쉬운 문제부터 풀어야 하므로 그냥 큐가 아니라 우선순위 큐로 위상 정렬을 한 후 출력하면 된다. Code #include #define ll long long using namespace std; ll N, M, chk[32005]; vector arr[32005]; void ..

문제 : 2056 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 �� www.acmicpc.net 각 작업의 수행 시간과 선행 작업을 할당받았을 때, 작업이 끝나는 최단시간을 출력하는 문제이다. 위상 정렬을 사용해 현재 작업할 수 있는 것부터 순차적으로 작업하면서 각 작업의 최소 시간을 구한 후 그중 최댓값을 찾으면 된다. Code #include #define ll long long using namespace std; ll N, M, T[10005], chk[10005], ans[10005]; vector arr[10..

문제 : 1516 게임 개발 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 건물을 짓는데 걸리는 시간과 그 건물을 짓기 전에 먼저 지어져야 하는 건물의 번호가 주어졌을 때, 그 건물을 짓는데 걸리는 최소 시간을 출력하는 문제이다. 위상 정렬을 사용해 현재 지을 수 있는 건물부터 순차적으로 지으면서 그 건물을 짓는 시간을 구해주면 된다. Code #include #define ll long long using namespace std; ll N, build[505], chk[505], ans[505..