기록방

👉 문제링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열이 있다. 두 수를 묶어서 곱셈 연산을 할 수 있고, 나머지는 합연산으로 계산한다. 계산 결과의 최대값을 출력한다. 🔸 문제 풀이 🔸 곱셈 연산으로 최대값을 만들어야 하므로 그리디 알고리즘으로 풀이한다. 수열을 정렬 후, 1보다 큰 수 중에서 크기가 큰 수를 우선으로 짝을 지어 곱셈 연산을 진행한다. 수가 1 미만인 수들은 음수끼리 만나 양수가 되거나, 0과 합쳐져 음수가 지워지므로 짝을 짓는다. 🔸 코드..

👉 문제링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 🔸 문제 분석 🔸 카드 묶음들을 합칠때 최소 비교 횟수를 출력한다. 🔸 문제 풀이 🔸 작은 묶음부터 합쳐야 최소값이 나오는걸 문제에서 확인할 수 있으므로, 그리디 알고리즘으로 접근해 우선순위 큐를 이용하여 풀이한다. 두 최소값 원소를 뽑아 그 합을 정답에 누적하고, 다시 그 합을 우선순위 큐에 넣는다. 우선순위 큐의 원소가 1개가 남을 때 까지 반복한다. 합으로 만들어진 새 묶음이 기존 묶음보다 클 수 있음에 유의한다. 🔸 코드 🔸 i..