https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
먼저, 그리디는 이 순간 가장 좋은 부분만을 고려해서 연산하는 것이 최적의 해가 되는 문제이다. 이게 말은 쉬운데, 증명이 어렵다. 물론, 쉬운 문제들은 굳이 증명하지 않아도 이게 그리디로 풀었을 때 최적해라는 것을 직관적으로 알 수 있다. 하지만, 문제가 어려워지면.. 아래와 같은 어려움이 따른다..
- 이게 그리디로 푸는게 최적해인지 가늠하기 어렵고(그리디가 최적해인지 증명하기 어렵고)
- 혹여나 그리디가 맞다면, 저 가장 순간의 좋은 부분만을 고려하는 아이디어를 떠올리기가 어렵다.
1. 동전 문제(#11047)
맞춰야 하는 돈에 대해 쓸 수 있는 가장 큰 단위의 돈부터 카운트함 (즉, 4,200원이면 1,000원부터 몇장을 최대 넣을수있는지 고려한다.) 즉, 갖고 있는 경우 중 가장 큰 단위의 동전부터 세면서, 타겟 금액보다 작거나 같은 경우에 해당 동전부터 먼저 최대로 count 하자.
동전 문제(#11047) 코드: https://github.com/brwnsugr/algorithm/blob/master/boj/11047_coins_greedy.cpp
2. 회의실 배정(#1931)
https://www.acmicpc.net/problem/1931
1931번: 회의실배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
사실 그리디라고 생각하고 풀면 쉬움. '당장 끝나는 시간이 가장 빠른 회의부터 우선 고려하여 카운트 해주는 것이 곧 최적해다. 그 다음 회의는 이전의 끝나는 시간 이후 + 끝나는 시간이 나머지 중에 가장 빠른 회의를 또 카운트해준다. 이런식으로 반복하여 계산하면 그것이 곧 해가 된다. ' 이를 위해서 회의의 끝나는시간과 시작시간을 벡터로 받아서 '매우 잘' 정렬해줘야 모든 케이스를 통과할 수 있다.
이를 테면, 아래와 같은 회의 종류를 인풋으로 받는다고 생각해보자. 총 3개 (5,5) (5,5), (2,5). 끝나는 시간이 같을 때는 시작시간이 더 빠른 순으로 꼭 정렬해줘야 2,5까지 카운트를 할 수 있다.
회의실 배정(#1931) 코드: https://github.com/brwnsugr/algorithm/blob/master/boj/1931_meeting_assign.cpp
3. ATM(#11399)
https://www.acmicpc.net/problem/11399
돈 뽑는 문제다. '가장 빨리 뽑을 수 있는 사람부터 앞에 배치' 한다고 가정할 때 계산되는 토탈 시간이 전체가 기다리는 시간이 최소가 되는 최적해가 된다. 누적 시간임을 감안하여 구현하자.
ATM (#11399) 코드: https://github.com/brwnsugr/algorithm/blob/master/boj/11399_atm.cpp
4. 잃어버린 괄호(#1541)
https://www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.
www.acmicpc.net
이게 왜 그리디에 있을까? + , - 두 개의 부호밖에 없다. 이 상황에서 괄호를 이용해 최솟값을 도출하기 위해선 '-'가 한 번 들어오면, 다음 '-'가 오기 전까지 모든 '+' 값들을 모두 괄호로 묶어 큰 값을 빼도록 해줘서 해당 '-' 연산을 극대화(?) 하는 알고리즘을 떠올리자. 사실 숫자가 양수 조건이기 때문에 가능한 것이다. 엣지 케이스들이 많을 수 있으니, 충분히 테스트를 해보고 제출하자. (string 처리하거나, 여러 잡일들이 많아서 내 기준으로 쉬운 문제는 아니다. 그렇다고 아주 어려운 문제도 아님..)
잃어버린 괄호 (#1541) 코드: https://github.com/brwnsugr/algorithm/blob/master/boj/1541_lost_bracket.cpp
5. 수 묶기(#1744)
https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열
www.acmicpc.net
그리디라고 가정하자.. (어차피 다루는 토픽이 그리디이니까). 즉, 최대가 될 수 있는 순간의 케이스만을 고려해보자.
대전제는 아래와 같다
묶는 숫자(서로 곱할 숫자)는 항상 최고값이 나오게 한다. + 묶기 전의 두 숫자의 합보다 당연히 묶은 후의 곱한 숫자가 더 커야 한다.(즉, 이득을 봐야 묶는다.) 이를 좀 더 쪼개서 생각해보면
- 음수끼리는 절대값이 큰 순서로 무조건 묶을수있는만큼 묶는다.
- 양수끼리는 걍 큰값끼리 묶을 수 있을만큼 묶는다.(*근데, 양 수값 중 1인 경우는 묶을 필요가 없다. 묶어봐야 오히려 숫자가 작아짐)
- 위의 내용대로 양수 값중 1은 어떤 숫자와도 묶지 않는다. (묶어봐야 더 작아지는 것은 생각해보면 알 수 있음)
- 0이 있는 경우, 위에서 묶고 나서 남은 음수와 묶어서 0으로 만들어준다.(그래야 -를 줄일수 있음)
위 방법을 코드로 구현하기 위해서는... 먼저 숫자들을 배열로 받아서 -> 정렬하자. 정렬해서 0보다 큰 파트와 0보다 작은 파트, 0으로 분류해서 0보다 큰 양수 파트 중 큰수끼리 최대한 다 묶고(단, 1은 제외), 0보다 작은 음수 파트에서는 절대값이 큰 부분부터 최대한 묶고, 0인 파트는 묶고 남은 음수가 있다면 그 음수와 묶어주자.
그냥 1을 제외한 양수 벡터, 음수 벡터, 그리고 1의 갯수, 0의 갯수, 총 2가지 벡터와 2가지 정수 자료형으로 쪼개서 담아서 연산해보자.
수묶기 (#1744) 코드: https://github.com/brwnsugr/algorithm/blob/master/boj/1744_binding_numbers.cpp
6. 대회 or 인턴(#2875)
https://www.acmicpc.net/problem/2875
2875번: 대회 or 인턴
문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여
www.acmicpc.net
인턴으로 참가시켜야하는 인원이 K일 때, 여자:N이나, 남자:M 중에 '당장 최대한의 팀을 꾸릴 수 있게 적절한 남, 녀를 한명씩 인턴으로 내보내고(N-- or M--) 그만큼 K를 깎으면서(K--) , K가 0이 되었을 때 (즉, 요구하는 인원을 인턴으로 다 내보냈을 때), 남은 인원으로 꾸릴수있는 대회 팀을 계산하면 된다.
여기서 핵심은 당장 최대한의 팀을 꾸릴 수 있게, 남, 녀를 적절히 선택하여 한명씩 인턴으로 내보내는 로직이다. 이 로직을 만족하며, 인원을 뺀다면 그게 곧 가장 많은 대회팀을 꾸릴 수 있는 최적해를 만족하므로 그리디 문제인 것이다.
저 로직을 구현하면, 아래와 같다. 참고로 K도 K--인 이유는, 남은 남녀 숫자를 1씩 줄이는 만큼 요구 인턴 인원도 그만큼 줄어야 하기 때문이다.(인원 보냈으니까 K도 줄여야지.)
- (남은 여자 인원) > (남은 남자 인원*2) 인 경우, 잉여 여자가 생기는 것이므로 여자를 인턴으로 뺀다.(N--, K--)
- (남은 여자 인원) < (남은 남자 인원*2) 인 경우, 잉여 남자가 생기는 것이므로 남자를 인턴으로 뺀다.(M--, K--)
- (남은 여자 인원) = (남은 남자 인원*2) 인 경우, 우선 여자를 빼주자. (여2, 남1로 꾸려야 하므로 우선은 여자를 빼줘보자...)
- 위 세가지 로직을 K==0이 될 때까지 반복한 다음, 남은 인원들로 꾸릴 수 있는 팀의 갯수를 구해준다.
대회 or 인턴 (#2875) 코드: https://github.com/brwnsugr/algorithm/blob/master/boj/2875_contest_or_intern.cpp
'알고리즘_개념 및 문제풀이 ' 카테고리의 다른 글
| BOJ/C++/DFS/BFS 문제풀이1/#2331(반복수열)/#9466(텀프로젝트)/ (0) | 2020.03.25 |
|---|---|
| BOJ 그리디 문제 모음2/C++/30(#10610)/병든나이트(#1783)/NMK(#1201) (0) | 2020.03.23 |
| 카카오/코딩테스트 기출/추석트래픽/2018 Blind Recruitment 1차/cpp(C++)풀이 (0) | 2020.03.08 |
| 리트코드(Leetcode)/Word_Ladder (0) | 2019.11.02 |
| 리트코드/leetcode/maxsubarray/부분최대합수열 (0) | 2019.10.05 |