문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2170: 선 긋기 문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 start, 끝을 end라고 하자. 선을 긋고 있을 때, 어떤 상황에서 다음 선을 한번에 그을 수 있을까? 만약 다음으로 그을 선의 시작이 end kantatatam.tistory.com 위의 문제가 생각나는 문제이다. A강의와 B강의가 서로 같은 강의실을 사용하려면 A강의가 B강의의 시작하는 시간보다 빨리 끝나야 한다. 오름차순 우선순위 큐를 만든다. priority_queue..
문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 그리디, 자료 구조, 우선순위 큐 2가지 방법으로 문제를 풀 수 있다. 1. 가방을 오름차순으로 정렬하고, 현재 가방에 넣을 수 있는 가격이 최대인 보석을 찾는 방법 보석과 가방을 오름차순으로 정렬한다. 용량이 적은 가방부터 현재 가방에 들어갈 수 있는 보석을 모두 우선순위 큐에 넣는다. 그렇게 되면, 우선순위 큐의 top에는 현재 가방에 들어갈 수 있으면서 가격이 최대인 보석이 위치하게 된..
문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 그리디 n이 5로 나누어 떨어진다면 5원으로 거스름돈을 채울 수 있다. 5로 나누어 떨어지지 않는다면 2원과 같이 채워야 한다. 1원이 아니라 2원이기 때문에, 5로 나눈 나머지를 2원으로 맞춰서 낼 수 없다. 예를 들어 1원 혹은 3원이 남았다면 2원으로 채울 수 없다. n이 5로 나누어 떨어지지 않는다면, n이 5로 나누어 떨어지거나 n이 0 이하가 될 때까지 2씩 차감한다. n이 0미만이 된다면, 거슬러 줄 수 없는 경우이다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin..
문제 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 그리디, 정렬 수열의 음수와 양수를 나눠서 생각한다. 음수의 경우 가장 작은 수를 둘씩 묶어야 하고, 양수의 경우 가장 큰 수를 둘씩 묶어야 한다. 추가적으로, 0이 입력된 경우도 생각해야 한다. 음수의 경우, 가장 작은 수를 둘씩 묶어야 한다. 음수의 개수가 홀수인 경우 0이 입력되었다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)는 0과 묶인다. 0이 입력되지 안않다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)를 정답에 더한다. 양수의 경우..
문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 그리디 가장 큰 자리수로 많이 입력된 알파벳이 9가 되어야 하고, 다음으로 적게 입력된 알파벳이 8이 되어야 한다. 이런 순서로 알파벳을 숫자로 변환한다. GCF가 입력되면 알파벳이 하나의 숫자라고 생각하면, GCF = G * 100 + C * 10 + F로 표현할 수 있다. ACDEB가 입력되면 ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B로 표현할 수 있다. 여기서 각 알파벳의 계수를 보면 다음과..
문제 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 그리디 기타 줄을 사는 경우는 총 3가지이다. 패키지만 사서 N줄을 채우는 경우 낱개만 사서 N줄을 채우는 경우 패키지와 낱개 혼합으로 사서 N줄을 채우는 경우 여기서 필요한 값은 패키지 가격의 최솟값, 낱개 가격의 최솟값이다. 3번의 경우 최솟값인 패키지를 (N / 6)개 구입해서 남은 줄인 (N % 6)줄을 낱개로 구입하는 것이 가격이 최소다. 위의 3가지 경우 중에서 최솟값을 구한다. 코드 #include #include using names..
문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 그리디, 정렬 먼저 서류심사 성적을 기준으로 정렬한다. 서류 성적 1등부터 7등을 0번부터 6등이라고 하자. 서류 면접 1 4 2 5 3 6 4 2 5 7 6 1 7 3 0번은 서류 성적이 1등 이므로, 면접 성적이 낮아도 서류 성적이 제일 높기 때문에 무조건 선발된다. 1번은 0번보다 서류 성적은 낮지만, 면접 성적이 높을 수 있다. 1번이 0번보다 면접 성적이 높다면 설발된다. 1번이 선발되었다고 가정하자. 마찬가지로, 2번은..
문제 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 그리디 0과 1의 구역 중에서 더 적은 수의 구역을 뒤집으면 된다. S[i]와 S[i + 1]의 문자가 서로 다르면, 한 구역이 종료된 것으로 S[i]의 구역 수를 1 증가한다. 문자열의 끝까지 검사하여, 개수가 더 적은 구역의 수를 출력한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); s..
문제 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 그리디 가장 작은 자연수인 1부터 N을 넘기 직전까지 더해간다. N이 200이면 다음과 같다. 1 + 2 + 3 + ... + 18 + 19 = 190 다음 수인 20을 더하면 210이므로 200을 초과한다. 여기서 더해지는 자연수는 중복되면 안 되므로, 마지막 수인 19를 29로 바꾸면 합이 200이 된다. 즉, 1부터 더한 값이 넘을 때까지의 자연수의 개수 - 1이 정답이다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ..
문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 그리디, 우선순위 큐 카드 수가 가장 적은 2개의 묶음을 합치는 방식으로 해결할 수 있다. 이 때, 2개의 묶음을 선택하기 위해, 우선순위 큐를 사용한다. 카드 수가 가장 적은 2개의 묶음을 합친다. 합쳐진 묶음을 다시 우선순위 큐에 넣는다. 모든 카드 묶음이 합쳐질 때까지 반복 코드 #include #include using namespace std; // 오름차순 우선순위 큐 priority_queue pq; int main() { ..
