https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 그리디 문제다. 주어진 수열에서 최대 합을 구하는 문제다. 합을 할 수 있는 방법은 1. 한 개의 수 더하기 2. 두 수의 곱 더하기 정렬을 해서 양수와 음수를 따로 계산하는 방법을 떠올렸다. 이와 비슷한 문제를 푼 적이 있는데 https://www.acmicpc.net/problem/1461 이 문제다. 수열을 입력 받으면서 음수의 개수를 세어두고, 수열을 정렬한다. 주의해야 할 점은 1. 큰 ..
Algorithm/Greedy
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 문제다. 멀티탭에 플러그를 꽂되, 플러그를 최대한 적게 빼는 횟수를 구하는 문제다. 입력된 멀티댑 사용 순서는 유지 해야 하므로 앞에서부터 접근했다. 1. 해당 플러그가 이미 꽂혀 있는지 확인 2. 플러그에 빈 자리가 있다면 꽂기 3. 빈 자리가 없다면 현재 꽂힌 플러그 중 가장 나중에 사용되는 플러그를 뽑는다. 3번을 처리하는 구현이 살짝 까다로웠지만 알고리즘 자체를 생각해내는데 어렵진 ..
https://www.acmicpc.net/problem/2879 2879번: 코딩은 예쁘게 첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수 www.acmicpc.net 그리디 문제다. 근데 구현 문제 같다. 코드의 인덴트를 맞추는 문젠데 드래그 후 탭을 누르는 횟수를 최소로 만들어야 한다. 탭을 추가해야 하는 경우와 삭제해야 하는 경우를 나눠서 생각했다. (양수와 음수) 추가해야 하는 경우 결과 값과 현재 값의 차이가 양수다. 이 때 이전 값이 음수라면 res에 현재 값을 더해준다. 이전 값이 양수라면 두 가지 경우로 나뉜다. 이전 값보다 현..
https://www.acmicpc.net/problem/7983 7983번: 내일 할거야 내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다. www.acmicpc.net 그리디 문제다. 과제를 최대한 미뤄 내일부터 연속으로 최대 며칠 놀 수 있는지 구하는 문제다. 최대한 뒤로 미뤄야하기 때문에 맨 뒤에서부터 채워나갔다. 우선 마감일을 기준으로 정렬을 했다. 내림차순으로 데이터가 필요하지만 오름차순으로 정렬하고 뒤에서부터 접근했다. 마지막 마감일을 기준으로 걸리는 일수를 빼주고 그 후로는 이전 과제 시작일과 해당 과제 마감일 중 작은 값을 해당 과제의 마감일로 계산했다. 최종적으로 마감일이 가장 빠른 과제..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디 문제다. 수의 곱과 합으로 최대값을 찾는 문제이므로 정렬을 먼저 했다. 처음에는 정렬 후 큰 수부터 곱과 합의 크기를 비교하고 큰 쪽으로 결과 값에 더해주는 방식으로 했다. 이 때 곱이 크면 인덱스를 하나 더 줄여주고, 합이 크면 현재 인덱스의 값만 더한다. (쓰다보니 필요 없는 부분인가 싶다) 간과한 점은 음수도 들어올 수 있다는 점이다. 음수의 경우 작은 음수끼리 곱할 수록 값이 커진..
https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 그리디 문제다. 화물의 무게와 크레인의 무게를 정렬한 후 무게 제한이 큰 크레인부터 화물을 담았다. 벡터를 이용했고, 크레인에 화물을 담을 때, 화물을 벡터에서 제거했다. #include #include #include using namespace std; int limit[50]; vector box; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_..
