[코테/백준] Python 수 묶기 - 1744번

실패 | 시도 - 번

 

🔗 [백준] 1744번 수 묶기

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

4. 문제 풀이 / https://velog.io/@slbin-park/%EB%B0%B1%EC%A4%80-1744%EB%B2%88-%EC%88%98-%EB%AC%B6%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀