목록Algorithm/Greedy (26)
우노
문제 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 예를 들어 순선대로 2, 4, 5, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 +6 +5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, ..
문제 링크 https://www.acmicpc.net/problem/1744 풀이 최댓값을 유도하기 위해선 양수와 음수는 서로 곱해야한다. 양수 묶음의 경우, 큰 수끼리 곱해야한다. (ex. 5, 4) 음수 묶음의 경우, 절대값이 큰 음수끼리 곱해야한다. (ex. -5, -4) 1 은 어떠한 경우든, 묶어서 곱셈하는 결과값보다, 개별로 덧셈하는 결과값이 더 크다. 0 을 개별로 더하는 것은 무의미하므로, 음수의 개수가 홀수일 경우, 가장 절대값이 작은 음수와 0 을 곱해주는 방식이 최댓값 유도에 좋다. (ex. -1 * 0) 풀이 방법 양수들은 positive 벡터에 저장하고, 음수들은 negative 벡터에 저장한다. 0 의 개수는 개별 변수로 저장하고, 1 은 모두 총 결과값에 더해준다. 이후, po..
문제 링크 https://www.acmicpc.net/problem/13305 풀이 예제 그림 문제는, 현재 도시의 주유 가격이 다음 도시의 주유 가격보다 비싼지, 저렴한지에 따라 나뉘게 됩니다. 현재 주유소보다 다음 주유소가 싸다면, 현재 주유소에서는, 다음 주유소로 이동하는 데에 걸리는 거리만큼만 주유하고, 다음 주유소에서 더 주유하는 것이 이득입니다. 만약, 현재 주유소가 다음 주유소보다 싸다면, 다음 주유소에서 다다음 주유소까지 이동하는 데에 걸리는 거리만큼, 현재 주유소에서 더 주유하는 것이 이득입니다. 즉, 도시를 이동할 때마다 기름을 채워주되, 이전에 등장했던 주유 가격 중 가장 최소의 가격으로 기름을 채울지, 현재 주유소의 가격으로 기름을 채울지만 정하면 됩니다. 주의 사항 첫 번째 도시에..
문제 링크 https://www.acmicpc.net/problem/10162 풀이 초단위의 요리시간이 입력으로 들어왔을 때, 요리 시간이, A 버튼의 시간인 300초보다 크다면, 요리 시간을 300초로 나눈 뒤, 나눠진 몫을 A 버튼 사용 개수로 저장하고, 나머지를 남은 요리시간으로 저장합니다. 남은 요리 시간이, B 버튼의 시간인 60초보다 크다면, 요리 시간을 60초로 나눈 뒤, 나눠진 몫을 B 버튼 사용 개수로 저장하고, 나머지를 남은 요리시간으로 저장합니다. 남은 요리 시간이, C 버튼의 시간인 10초보다 크다면, 요리 시간을 10초로 나눈 뒤, 나눠진 몫을 C 버튼 사용 개수로 저장합니다. 이후에도 요리 시간이 남는다면, -1 을 출력합니다. 코드 #include using namespace ..
문제 링크 https://www.acmicpc.net/problem/11000 풀이 해당 문제를 풀기 위해, 요소 삽입과 동시에 내부 요소를 정렬하는 Priority Queue 라는 자료구조를 사용했으며, 개념에 대해선 추가적인 숙지가 필요합니다. https://wooono.tistory.com/392 이제, 문제에서 주어진 예제 (1,3) (2,4) (3,5) 를 통해서 풀이해보겠습니다. 우선 수업 목록을, 시작 시간 기준으로 오름차순 정렬합니다. 그 다음, 시작시간이 가장 빠른 수업(1, 3) 의 종료시간(3) 을 Priority Queue 에 push 합니다. 그리고, 두 번째로 시작시간이 빠른 수업(2,4) 의 종료시간(4) 을 Priority Queue 에 push 합니다. 이제, Priorit..
문제 링크 https://www.acmicpc.net/problem/11047 풀이 동전 배열을 마지막 idx 부터 역순으로 탐색 남은 금액이 해당 idx 의 동전보다 크거나 같다면, 남은 금액에서 해당 idx 금액 만큼을 차감하고 동전 개수 + 1 마지막으로 탐색한 idx 부터 1~2번을 반복하며, 남은 금액이 없을 때까지 무한 루프 코드 #include #include using namespace std; vector coin_list; // 목표 금액까지 몇 개의 동전이 필요한지 출력해주는 함수 int greedy(int remain_cost){ // 목표 금액까지 필요한 동전 개수 int count = 0; // 동전 배열을 끝에서부터 탐색하기 위한 idx int idx = coin_list.si..