블로그 언저리인 무언가

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

오늘은 음력 8월 15일 추석이다. 뭔가 작년에는 추석이 엄청 빨랐던 것 같아서 찾아보니까 9월 13일이었다. 위키백과 켜서 연도별 일정 확인해보니까 거의 다 9월 중순~말이던데 웬일로 이런 걸 기억하고 있는지 모르겠다. 42 서울은 결국 라피씬 일정이 10월 5일에서 10월 12일로 밀렸다. 코로나 19 추석 특별방역기간 때문에 50인 이상 모이는 게 불가능해서 뒤로 밀렸는데, 1단계로 내려가면 전일제, 2단계 유지라면 격일제, 3단계로 올라가면 해제 때까지 연기된다고 한다. ACM-ICPC 예선이 다음 주 금요일이라 차라리 밀린 게 나은 거 같기도 한데 이러다 영원히 밀려서 기말까지 가지만 않았으면 좋겠다. 그래도 요즘에는 하루에 1~2문제씩 골드 정도 난이도로 꾸역꾸역 풀고 있기는 하다. 구현 문제..

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