Algorithm/그리디11 [백준] 1715 카드 정렬하기 c++ 문제 링크 https://www.acmicpc.net/problem/1715 KEY 우선순위 큐를 활용하는 간단한 문제이다. 두 카드묶음을 선택할 때, 순서대로 고르지 않아도 되고 무작위로 두개를 선택해도 되므로, 스택(stack)이 아닌 우선순위 큐(priority_queue)를 사용한다. N의 조건이 1부터 100,000이라서 N이 1일때도 고려해야 하는데 1일때를 고려해서 풀면 오히려 오답이 나온다..🤔 Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include #include #include #include using namespace st.. 2023. 3. 21. [백준] 1946 신입사원 c++ 문제 링크 https://www.acmicpc.net/problem/1946 KEY 그리디 유형의 문제의 상당 부분은 정렬을 통해서 풀 수 있는데, 이 문제 역시 벡터의 정렬을 통해 해결할 수 있다. 서류순위, 면접순위 두 가지를 고려해야 하므로 서류순위를 오름차순으로 정렬하여 고정한 후, 면접 순위만을 고려하면 된다. 서류순위를 오름차순 정렬했기 때문에 면접순위를 고려할 때, n번째 신입사원은 1 ~ n-1번째 신입사원의 면접순위보다 높아야 한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include #include #include #inc.. 2023. 3. 20. [백준] 11047 동전0 c++ 문제 링크 https://www.acmicpc.net/problem/11047 KEY 금액이 큰 단위부터 K값을 비교해 나가야 동전 개수가 최소가 된다. 따라서 금액 단위를 내림차순 정렬만 하면 되므로, 쉽게 접근할 수 있던 문제였다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include #include #include #include using namespace std; int N,K; vector v; int answer; int main() { cin >> N >> K; for (int i = 0; i > coin; v.push_back(coin); } sort(.. 2023. 3. 20. [백준] 2839 설탕 배달 c++ 문제 링크 https://www.acmicpc.net/problem/2839 KEY 3과 5중에 5로 나누어 떨어지게 하는 것이 최소가 된다. 그리디 풀이 그리디 풀이의 경우 가령 18이 주어졌을 때, 5로 먼저 나누어 떨어지는지 보고, 아니라면 3씩 빼준다.(+1) 15가 되었을 때 5로 나누어 떨어지므로, 나눈 몫만큼 더해주면 (+3) 총 4번으로 배달 할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include #include #include using namespace std; int N; int answer; int main() { cin >> N; while (N >= 0) { if (N % 5 .. 2023. 3. 15. [백준] 11000 강의실 배정 c++ 문제 링크 https://www.acmicpc.net/problem/11000 풀이 방법 먼저 시작하는 회의 순으로 정렬한다. 회의가 끝나는 시간을 저장하는 우선순위 큐(pq)를 하나 만든 후, 맨 앞의 회의가 끝나는 시간을 저장한다. 지금 회의가 pq의 top이후에 시작한다면(같은 회의실을 사용할 수 있다면) pq의 top을 꺼내고, 지금 회의의 끝나는 시간을 pq에 push한다. 그게 아니라면(다른 회의실을 사용해야 한다면) 회의가 끝나는 시간을 pq에 push한다. 모든 회의를 순회했을 때 결국 pq의 size가 회의실 갯수가 될것이다. 구현은 어렵지 않았으나 풀이 방법이 생각이 안나서 굉장히 까다로웠던 문제였다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 2022. 2. 2. 백준 1343 폴리오미노 효율적인 방법이라고 생각이 들진 않지만 다른 풀이와 비교했을 떄 시간복잡도가 괜찮은것같아서 풀이를 수정하지 않았다. 풀이방법 "XX"가 나오면 "BB"로 교체한다. "."가 나오면 result 값을 지우고 continue한다. 이렇게 완성된 문자열은 예를들어서 BBX.BB 이런 형태를 띌것이다. 이 완성된 문자열을 가지고 "BBBB"가 나오면 "AAAA"로 교체한다. "."가 나오면 result2값을 지우고 continue한다. 완성된 문자열에서 X가 하나라도 있다면 A,B로 만들수 없다는 뜻이므로 -1출력. Key point 핵심이랄 것 까지는 없는 것같고 문자열처리를 잘 해야했다. string의 replace, find함수를 사용할 수 있는 문제다. 2022. 2. 1. 이전 1 2 다음
