오늘 문제는 문제를 통해 얻어낼 수 있는 특징들을 확실히 찾아야 풀 수 있는 문제입니다. 이런 연습이 꼭 필요하다고 생각합니다. 그럼 문제를 살펴 볼까요?
1. 오늘의 학습 키워드
- 정렬
- 그리디 알고리즘
2. 문제: 1744. 수 묶기
- 단계: 🥇 골드 4단계
- 주제:
- 출처: https://www.acmicpc.net/problem/1744
문제
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.
예제 입력 1 복사
4
-1
2
1
3
예제 출력 1 복사
6
예제 입력 2 복사
6
0
1
2
4
3
5
예제 출력 2 복사
27
예제 입력 3 복사
1
-1
예제 출력 3 복사
-1
예제 입력 4 복사
3
-1
0
1
예제 출력 4 복사
1
예제 입력 5 복사
2
1
1
예제 출력 5 복사
23. 문제 풀이
Step1. 문제 이해하기
이 문제는 수열의 모든 수를 적절히 묶어서 합을 최대화하는 문제입니다.
수를 묶는 규칙에 따라 계산해야 하는 점이 중요하며, 주어진 수열의 특징을 잘 활용하는 것이 핵심입니다.
입 출력을 살펴보도록 하겠습니다.
- Input:
- 첫째 줄에 수열의 크기 N이 주어집니다. N은 50보다 작은 자연수입니다.
- 둘째 줄부터 N개의 줄에 수열의 각 수가 주어집니다.
- 수열의 수는 -1000보다 크거나 같고, 1000보다 작거나 같은 정수입니다.
- Output: 수를 합이 최대가 나오게 묶었을 때 합을 출력합니다. 정답은 항상 보다 작다고 합니다. 이는 int형 정수가 나온다는 것을 의미합니다.
Step2. 문제 분석하기
해당 문제에서 수열을 구성하는 수들은 음수도 올 수가 있습니다.
묶여진 수열들은 곱셈을 합니다. 그렇기 때문에 양수냐, 음수냐에 따라 구분을 해야 합니다.
- 양수:
- 양수 중 1을 제외한 수는 곱할수록 값이 커지므로 큰 수들끼리 묶는 것이 유리합니다.
- 1은 곱하기보다는 더하는 것이 이득입니다.
- 음수:
- 음수는 절댓값이 큰 수들끼리 묶어 곱하면 더 큰 양수로 전환되거나 손실을 줄일 수 있습니다.
- 묶은 음수가 홀수개라면 남은 음수는 0과 곱해 제거하는 것이 유리합니다.
- 0:
- 0은 남은 음수를 제거하는 데 사용할 수 있습니다.
- 즉, 남은 음수가 있을 경우 0과 묶도록 합니다.
- 1:
- 1은 곱하기보다 더하기가 이득이므로 따로 합산합니다.
위 내용을 기반으로 코드를 설계하겠습니다.
Step3. 코드 설계
- 입력 처리:
- 수열을 입력받아 양수, 음수, 0, 1로 분류합니다.
- 양수와 음수 정렬:
- 양수는 내림차순으로 정렬하여 큰 값부터 묶습니다.
- 음수는 오름차순으로 정렬하여 절댓값이 큰 음수끼리 묶습니다.
- 합산 처리:
- 양수 리스트에서 2개씩 묶어 곱한 후 합산합니다. 묶고 남은 값은 더합니다.
- 음수 리스트에서 2개씩 묶어 곱한 후 합산합니다. 묶고 남은 값은 0이 없으면 더합니다.
- 1은 따로 합산합니다.
- 결과 반환:
- 계산한 최대 합을 반환합니다.
Step4. 코드 구현
import sys
N = int(sys.stdin.readline().strip())
nums = [int(sys.stdin.readline().strip()) for _ in range(N)]
def sol(N, nums):
positive = []
negative = []
zeros = 0
ones = 0
for num in nums:
if num > 1:
positive.append(num)
elif num == 1:
ones += 1
elif num == 0:
zeros += 1
else:
negative.append(num)
positive.sort(reverse=True)
negative.sort()
total_sum = 0
for i in range(0, len(positive) - 1, 2):
total_sum += positive[i] * positive[i + 1]
if len(positive) % 2 == 1:
total_sum += positive[-1]
for i in range(0, len(negative) - 1, 2):
total_sum += negative[i] * negative[i + 1]
if len(negative) % 2 == 1:
if zeros == 0:
total_sum += negative[-1]
total_sum += ones
return total_sum
print(sol(N=N, nums=nums))- 코드 설명:
- 입력된 수열을 양수, 음수, 0, 1로 분류합니다.
- 양수는 내림차순으로 정렬하여 두 개씩 곱하고, 남은 값은 더합니다.
- 음수는 오름차순으로 정렬하여 두 개씩 곱하고, 남은 값은 0이 없으면 더합니다.
- 1은 곱하지 않고 더합니다.
- 시간 복잡도:
- 결과:
4. 마무리
이번 문제는 수열의 특징을 분석하여 최적의 전략을 세우는 그리디 알고리즘의 전형적인 유형입니다.
핵심은 양수는 큰 값끼리 곱하고, 음수는 절댓값이 큰 값끼리 묶으며, 1은 더하고, 0은 음수를 제거하는 방식으로 접근하는 것입니다.
이를 통해 문제를 효율적으로 해결할 수 있으며, 정렬과 간단한 반복문으로 시간 복잡도도 적절히 관리할 수 있었습니다. 🎯
글 읽어주셔서 감사합니다.
