[ 백준 1744 해설 ] ( python ) 수 묶기

 

📚 수 묶기

 

문제

길이가 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이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열의 크기 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 복사

2

 

 

 

 

 

 

✍ 접근

• 그리디
• N 값이 크지 않고 큰 값끼리 곱해서 더하는 것이 가장 효율적인 방법이라는 기본 상식이 있기 때문에 그리디 알고리즘이라고 생각하고 풀었습니다

 

 

 

 

정답코드

# ✨ 입력
import sys
from itertools import combinations
input = sys.stdin.readline
N = int(input())

# ✨ 준비 1
arr = []
m_arr = []
res = 0
for _ in range(N):
    x = int(input())
    if x <=0:
        m_arr.append(x)
    elif x == 1:
        res+=1
    else:
        arr.append(x)
        
# ✨ 준비 2
m_arr.sort()
arr.sort(reverse = True)

# ✨ 풀이
if len(arr) %2 !=0:
    arr.append(1)
if len(m_arr)% 2 !=0:
    m_arr.append(1)
for i in range(0,len(arr),2):
    res+=(arr[i]*arr[i+1])
for i in range(0,len(m_arr),2):
    res+=(m_arr[i]*m_arr[i+1])
print(res)

 

해설

입력

• 문제에서 나온 값을 입력받는다

준비 1

• 수열을 돌면서 마이너스, 0일 때
  => m_arr(마이너스 배열)에 업로드
• 1일 때
  => 바로 res에 1 추가 (1은 곱하는 것보다 더해야 더 큰 값을 만들 수 있기 때문)
• 1보다 클 때
  => arr(플러스 배열)에 업로드

준비 2

• m_arr은 그냥 sort해줘도 된다
• arr은 reverse를 이용해서 sort해주고(큰 값들이 먼저 나오게)

 

풀이

• 만약 arr / m_arr에 홀수개가 들어있다면
  => 둘 다 뒤에 1을 append해줍니다 
  => 마지막에 등장하는 값 (m_arr같은 경우는 가장 큰 값 / arr의 경우는 가장 작은 값)을 각각 빼주고/더해주는 것이 낫기 때문에
• 그 후 for문을 돌면서 0부터 배열의 길이까지, 2씩 뛰면서 res에 묶은 값을 더해줍니다
• 그리고 res를 출력하면 자연히 가장 큰 값이 만들어져 출력됩니다.

 

 

⭐ 배움

• 그리디!!!😖