https://www.acmicpc.net/problem/1082 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net DP와 그리디 문제라고는 하는데 큰 수 연산이 필요할 것 같아 DP를 사용하지 않았다. 그리디 같은 구현 같은 그런,,, 방 번호가 크기 위해서는 자리수가 많은 게 제일 중요하다고 생각했고, 그 후 숫자가 큰 게 중요하다 생각했다. 숫자를 가격 기준으로 오름차순 정렬 후 가장 싼 값으로 배열을 채웠다. 나누기 연산을 이용했고 몫만큼 배열을 채운 후, 나머지만큼 큰 숫자로 바꿨다. 배열의 결과값이 모두 0인 경우 예외처리를 했다. 0이 하나인 경우 0 출력한다. 0이 2..
그리디
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선수위 큐와 그리디 문제다. 처음에는 작은 수가 여러 번 더해지는 게 최솟값이 나올 거라고 생각해 정렬 후 각 수에 n - i를 곱해서 더하는 방법을 생각했다. 이 방법은 항상 앞의 두 수 합에 바로 뒤에 숫자를 더한다. 반례가 있을 것 같다는 생각이 들었다. (a + b) (c + d) e 를 더하는 것이 최솟값이 나오는 경우가 있을 것 같았다. 있었다. 원소 삽입마다 정렬이 되..
https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 그리디 문제다. 스위치를 작동하는 가장 효율적인 방법은 순차적으로 탐색하되 지나간 전구는 건드리지 않는 것이다. 즉, n번째 전구를 바꾸기 위해서는 n+1번째 스위치를 작동하는 것이다. 이 방법으로 문제를 해결하려고 하면 첫 번째 스위치에 대한 의문이 생긴다. 첫 번째 스위치는 이전 전구가 존재하지 않으므로 작동 여부를 판별할 수 없다. 때문에 전구 탐색을 두 번 진행..
https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 그리디 문제다. 두 사람의 두 점수를 비교 했을 때 한 점수는 낮고 한 점수는 높아야 한다. 두 등수 중 하나를 기준으로 정렬하고 다른 등수가 전 사람보다 높은지 판별하면 된다. 등수는 중복되지 않으니 정렬을 사용하지 않고 하나의 등수를 인덱스로 사용해도 된다. #include #include using namespace std; pair arr[100000]; int mai..
