실패 | 시도 - 번
1744 : [그리디 알고리즘] 수 묶기(py)
문제 설명
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.
문제 분석
정수들의 곱셈이 어떤 결과를 가져오는지 알 필요가 있다.
1) 양수 * 양수 = 양수
2) 음수 * 음수 = 양수
3) 양수 * 음수 = 음수
4) 양수 * 0 = 0
5) 음수 * 0 = 0
6) 양수 * 1 = 양수
7) 음수 * 1 = 음수
합이 크기 위해서는
- 양수 * 양수, 음수 * 음수 조합이어야 한다.
- 1은 양수를 곱하기 보단 더하기를 해주는 것이 값을 키울 수 있다.
- 0은 양수보단 음수에 곱하기해줘야 값을 유지할 수 있다.
입력
첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 2^31보다 작다.
입력과 출력 예시
입력 | 출력 |
4 -1 2 1 3 |
6 |
6 0 1 2 4 3 5 |
27 |
1 -1 |
-1 |
3 -1 0 1 |
1 |
2 1 1 |
2 |
- 어느 분이 친절하게 반례 리스트를 만들어주셨다.
내 소스
- 첫시도 : 실패 (구현 실패, 시간 부족)
plus_numbers = []
rest_numbers = []
sum_numbers = []
N = int(input())
for _ in range(N):
number = int(input())
if number > 0:
plus_numbers.append(number)
else:
rest_numbers.append(number)
plus_numbers.sort(reverse=True)
rest_numbers.sort()
for i in range(0, len(plus_numbers)-1, 2):
if (plus_numbers[i] == 1) or (plus_numbers[i+1] == 1):
sum_numbers.append(plus_numbers[i] + plus_numbers[i+1])
else:
sum_numbers.append(plus_numbers[i] * plus_numbers[i+1])
if len(plus_numbers) % 2 == 1:
sum_numbers.append(plus_numbers[-1])
for i in range(0, len(rest_numbers)-1, 2):
sum_numbers.append(rest_numbers[i] * rest_numbers[i+1])
if len(rest_numbers) % 2 == 1:
sum_numbers.append(rest_numbers[-1])
print(sum(sum_numbers))
소스 설명
plus_numbers = []
rest_numbers = []
sum_numbers = []
[1 - 3]
- plus_numbers, rest_numbers : 양수와 0, 음수 리스트로 나눈 이유는 sort 기준이 다르기 때문이다. 양수끼리의 곱셈은 큰 수들끼리 곱해야 합이 커지고 음수끼리의 곱셈은 작은 수끼리 곱해야 합이 커진다.
예)
양수끼리의 합 : 4 * 3 = 12
음수끼리의 합 : (-4) * (-3) = 12
- 0을 음수 리스트에 같이 넣어주는 이유는 음수와 0의 곱셈이 음수를 상쇄하기 때문이다.
- sum_numbers : 정수들의 연산 결과를 담기 위한 리스트이다.
N = int(input())
for _ in range(N):
number = int(input())
if number > 0:
plus_numbers.append(number)
else:
rest_numbers.append(number)
[4 - 10] : N의 크기만큼 for문을 돌려서 입력을 받는다. 입력받은 정수가 0보다 크면 plus_numbers 리스트에 넣고 0과 음수는 rest_numbers 리스트에 넣는다.
plus_numbers.sort(reverse=True)
rest_numbers.sort()
'''
Example
plus_numbers : [4, 3, 2, 1]
rest_numbers : [-5, -4, -3, -2, -1, 0]
'''
[11 - 12] : 양수 리스트는 내림차순으로, 0, 음수 리스트는 오름차순으로 정렬한다.
for i in range(0, len(plus_numbers)-1, 2):
if (plus_numbers[i] == 1) or (plus_numbers[i+1] == 1):
sum_numbers.append(plus_numbers[i] + plus_numbers[i+1])
else:
sum_numbers.append(plus_numbers[i] * plus_numbers[i+1])
[14 - 18]
- 정수 2개씩 연산을 해야하기 때문에 for문의 범위는 0 ~ len(plus_numbers) - 1이고 간격은 2이어야 한다.
예) plus_numbers = [4, 3, 2, 1] 일 때
(4 * 3) + (2 * 1) 가 되고 리스트 인덱스로 표현하면
(plus_numbers[0] * plus_numbers[1]) + (plus_numbers[2] * plus_numbers[3])이 된다.
- 양수 * 1 보단 양수 + 1이 값을 더 키우므로 plus_numbers[i]나 plus_numbers[i+1] 중에 하나가 1이면 덧셈을 하여 sum_numbers 리스트에 추가한다.
- plus_numbers[i]와 plus_numbers[i+1]가 1을 제외한 양수인 경우, 곱셈을 하여 sum_numbers 리스트에 추가한다.
if len(plus_numbers) % 2 == 1:
sum_numbers.append(plus_numbers[-1])
[19 - 20] : plus_numbers 리스트의 개수가 홀수인 경우, 마지막 원소는 for문 계산에 포함되지 않게 된다. 그래서 리스트의 개수가 홀수일 때는 sum_numbers에 plus_numbers의 마지막 원소를 추가해준다.
예) plus_numbers = [3, 2, 1] 일 때
for문에서는 3과 2에 대한 처리를 해주고 for문이 끝나버린다.
for i in range(0, len(rest_numbers)-1, 2):
sum_numbers.append(rest_numbers[i] * rest_numbers[i+1])
if len(rest_numbers) % 2 == 1:
sum_numbers.append(rest_numbers[-1])
print(sum(sum_numbers))
[22 - 26]
- 양수 리스트와 다르게 0, 음수 리스트는 정수 2개씩 곱해주면 된다.
- 리스트 안에 0이 있더라도 어차피 음수와 곱셈을 하기 때문에 음수가 상쇄되어 문제가 없다.
- 마찬가지로, rest_numbers의 개수가 홀수인 경우, rest_numbers의 마지막 원소를 sum_numbers 리스트에 추가해준다.
- sum_numbers 리스트 원소들의 합을 출력한다.
다른 코드 분석
- 나는 1을 if문으로 양수 리스트에 있는지 확인하여 처리했는데 다른 분들은 정수를 입력받을 때부터 1인 경우, 다른 변수에 저장하고 양수 리스트에는 2 이상의 양수들로 구성하였다. 다른 분들처럼 애초에 양수와 0, 음수 리스트를 나눌 때 1에 대한 처리를 하는 것이 더 깔끔한 것 같다.
- 리스트의 개수가 홀수일 때 처리해주는 방식이 다양한 것을 알 수 있었다.
- [4] 작성자분은 pop()을 사용하여 합을 구하였다.
회고
- 처음 문제를 풀 때 양수, 0, 음수 모두를 한 리스트에 넣어서 풀었다. 모두를 한 리스트에 넣으니 음수 계산이 까탈스러워졌다. 그래서 양수와 0, 음수 리스트로 나눠서 계산할까 했는데 그러면 시간복잡도가 엄청 복잡해질 것 같아서 포기했었다. 다른 분들의 아이디어를 보니 나와 같은 생각을 갖고 풀어서 다시 생각했던 대로 문제를 푸니 성공했다. 숫자의 범위가 작아서 가능했던 것 같다.
Ref.
1. 문제 풀이 / https://cijbest.tistory.com/9
2. 문제 풀이 / https://jokerldg.github.io/algorithm/2021/03/15/number-tie.html
3. 문제 풀이 / https://data-flower.tistory.com/44
* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀
'코딩테스트' 카테고리의 다른 글
[코테/백준] Python 기타줄 - 1049번 (0) | 2023.01.27 |
---|---|
[코테/백준] Python 캠핑 - 4796번 (0) | 2023.01.27 |
[코테/백준] 레벨 기록 (0) | 2023.01.27 |
[코테/백준] Python 30 - 10610번 (0) | 2023.01.24 |
[코테/백준] Python ATM - 11399번 (0) | 2023.01.12 |