https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
이 문제는 전형적인 그리디 알고리즘 문제다.
그리디 알고리즘은 선택의 순간마다 당장의 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
최적값을 구하는데 사용되는 방법이다.
문제에서는 수를 적절히 묶어 최대 값이 나오게 하는 것이 최적 값이다.
보통 이런 문제는 첫째 줄에 수열의 크기가 주어진다. 둘째 줄부터는 n개의 수가 주어진다.
우리는 이 문제를 풀때 몇 가지 상황을 고려해야 한다.
1. 주어진 숫자가 짝/홀수 일 때
2. 음수와 짝수를 처리하는 방법
3. 1을 처리하는 방법
1번부터 설명을 하면 주어진 숫자가 짝수면 전부 묶을 수 있지만 홀수면 숫자 하나가 남아서 남은 숫자를 어떻게 할지 생각해야 한다.
2번은 음수와 짝수를 묶으면 더 큰 음수가 되므로 음수는 음수끼리 묶고 짝수는 짝수끼리 묶어야 한다.
3. 1은 묶으면 결과적으로 손해다. 1 * 3은 3이지만 1 + 3은 4다. 1을 처리하는 방법도 생각해야한다.
코드와 함께 설명하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import sys
input = sys.stdin.readline
num = int(input())
positive_num = []
negative_num = []
result = 0
for _ in range(num):
number = int(input())
if number > 1:
positive_num.append(number)
elif number == 1:
result += 1
else:
negative_num.append(number)
positive_num.sort(reverse=True)
negative_num.sort()
|
cs |
우선 나는 리스트를 두 개 만들어서 양수와 음수를 따로 관리했다.
숫자가 1보다 클 때는 양수 리스트에 넣고 숫자가 1일 때는 결과값에 1을 더했다.
*숫자가 1일때 1을 더하는 이유는 위에 있는 3번에 있습니다.
숫자가 0 또는 음수일 때는 음수 리스트에 넣었다.
그 후, 양수 리스트는 sort함수에서 reverse=True를 함으로 내림차순으로 정리하였다.
음수 리스트는 sort함수를 사용해서 오름차순으로 정리하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
if len(positive_num) % 2 == 1:
for i in range(0,(len(positive_num)//2)):
first = positive_num.pop(0)
second = positive_num.pop(0)
result += first * second
result += positive_num.pop()
else:
for i in range(0,(len(positive_num)//2)):
first = positive_num.pop(0)
second = positive_num.pop(0)
result += first * second
|
cs |
우선 양수리스트는 내림차순으로 정리되어있기 때문에 리스트에서 맨 앞에 있는 숫자를 두 개 추출해서 결괏값에 곱한 값을 더하는 방식으로 처리했다.
양수리스트의 길이가 홀수일 때는 맨 마지막에 있는 숫자(가장 작은 숫자)는 결과값에 더했다.
|
1
2
3
4
5
6
7
8
9
10
11
|
if len(negative_num) % 2 == 1:
for i in range(0,(len(negative_num)//2)):
first = negative_num.pop(0)
second = negative_num.pop(0)
result += first * second
result += negative_num.pop(0)
else:
for i in range(0,(len(negative_num)//2)):
first = negative_num.pop(0)
second = negative_num.pop(0)
result += first * second
|
cs |
음수리스트일 때도 양수리스트일 때와 똑같이 맨 앞에 있는 숫자 두개를 추출한 뒤 결과값에 곱하는 방식으로 처리했다.
길이가 홀수일 때는 맨 마지막에 있는 숫자(가장 작은 숫자)는 결과값에 더했다.
정답코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import sys
input = sys.stdin.readline
num = int(input())
positive_num = []
negative_num = []
result = 0
for _ in range(num):
number = int(input())
if number > 1:
positive_num.append(number)
elif number == 1:
result += 1
else:
negative_num.append(number)
positive_num.sort(reverse=True)
negative_num.sort()
if len(positive_num) % 2 == 1:
for i in range(0,(len(positive_num)//2)):
first = positive_num.pop(0)
second = positive_num.pop(0)
result += first * second
result += positive_num.pop()
else:
for i in range(0,(len(positive_num)//2)):
first = positive_num.pop(0)
second = positive_num.pop(0)
result += first * second
if len(negative_num) % 2 == 1:
for i in range(0,(len(negative_num)//2)):
first = negative_num.pop(0)
second = negative_num.pop(0)
result += first * second
result += negative_num.pop(0)
else:
for i in range(0,(len(negative_num)//2)):
first = negative_num.pop(0)
second = negative_num.pop(0)
result += first * second
print(result)
|
cs |