블로그 언저리인 무언가

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

문제 : 17251 힘 겨루기 17251번: 힘 겨루기 과거 격투가로 명성을 떨치던 힘스트롱씨는 "힘 겨루기"라는 대회를 주최하여 전국에 홍보를 하였다. 모집 공고를 보고 전국 각지에서 많은 사람들이 모였는 데, 모집 공고에 '힘'이란 것에 대해 www.acmicpc.net 기준선을 기준으로 양측에서 가장 힘이 센 사람이 나와 힘을 겨룰 때, 어느 쪽이 이길 확률이 더 높은지 찾는 문제이다. 가장 힘이 센 사람의 위치를 체크해 그 사람이 나오기 전과 후로 나누어 확인하면 된다. 여러 명인 경우에는 맨 처음 사람과 맨 끝의 사람 전후를 비교하면 된다. Code #include #define ll long long using namespace std; ll N, mx, idx1, idx2; int main(..

문제 : 2879 코딩은 예쁘게 2879번: 코딩은 예쁘게 첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수� www.acmicpc.net 소스코드의 현재 탭의 개수와 원하는 탭의 개수가 주어질 때, 연속된 줄을 그룹을 선택해 편집하는 최소 횟수를 구하는 문제이다. 그리디 알고리즘을 활용해 한번 탭을 추가하거나 삭제할 때 현재 줄부터 가장 뒤의 줄까지 중 가장 많은 탭 개수를 한 번에 조절할 수 있는 위치를 찾아 처리해주는 것을 반복하면 된다. Code #include #define ll long long using namespace std; l..

문제 : 1577 도로의 개수 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은 �� www.acmicpc.net 도시의 크기가 주어지고 공사 중인 도로의 크기가 주어졌을 때, (0,0)에서 (N, M)까지 가는 경우의 수를 출력하는 문제이다. 도로가 정상적일 때 현재 위치기준 왼쪽+아래가 경우의 수 이므로 공사중인 도로인지 아닌지 체크하며 DP 배열을 채우면 된다. Code #include #define ll long long using namespace std; struct ABC{ ll a, b, c, d; ABC(){..

문제 : 14370 전화번호 수수께끼 (Large) 14370번: 전화번호 수수께끼 (Large) 첫 줄에 테스트케이스의 개수 T가 주어진다. 각 테스트케이스에는 상대방이 제시한 스트링 S가 주어진다. S는 영어 대문자로만 이루어져 있다. 1≤ T ≤ 100이고, S의 길이는 3 이상 2000 이하이다. www.acmicpc.net 전화번호의 각 자리를 영단어로 바꾸고 이를 뒤섞은 문자열이 주어졌을 때, 원래 전화번호를 알아내는 문제이다. 각 영어로 된 숫자들에서 유일한 문자를 가진 것들을 먼저 찾아내고 그 숫자를 제거했을 때 다시 유일한 문자들을 가진 숫자를 제거하는 식으로 진행하면 0-2-4-6-8-1-3-5-7-9 순서로 구하면 된다는 것을 알 수 있다. Code #include #define ll..