알고리즘/BOJ
[BOJ 1744, Python 3] 수 묶기
70825
2021. 8. 11. 21:40
반응형
https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
풀이
간단한 그리디 + case work 문제 같습니다.
1. 1을 제외한 양수
양수에서 큰 값 2개를 계속 곱하다가 나중에 1개만 남으면 남은 한 개는 더해주면 됩니다.
2. 1일 때
1 * 7 보다 1 + 7이 더 크기 때문에 1은 전부 더해주기만 합니다.
3. 음수의 개수가 짝수일 때
제일 작은 수 2개끼리 계속 곱해주면 됩니다.
4. 음수의 개수가 홀수일 때
3번처럼 제일 작은 수 2개끼리 곱해줘서 1개가 남기면 됩니다.
이 1개는 수열에 0이 있으면 (음수) * 0 = 0으로 만들 수 있습니다.
하지만 수열에 0이 없으면 음수를 답에 더해줘야 합니다.
1의 경우를 생각 못해서 많이 틀리다가 통과했네요
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
n = int(input())
arr = [int(input()) for _ in range(n)]
plus = sorted([arr[i] for i in range(n) if arr[i] > 1])
minus = sorted([arr[i] for i in range(n) if arr[i] <= 0], reverse=True)
zero = [arr[i] for i in range(n) if arr[i] == 0]
one = [arr[i] for i in range(n) if arr[i] == 1]
ans = 0
while plus:
x = plus.pop()
if not plus: ans += x
else: ans += x * plus.pop()
while len(minus) > 1:
x = minus.pop()
if minus: ans += x * minus.pop()
ans += len(one)
if not zero and minus: print(ans + minus[0])
else: print(ans)
|
cs |
반응형