백준 28062 (준석이의 사탕 사기) [Python/파이썬] [Greedy/그리디]

https://www.acmicpc.net/problem/28062

28062번: 준석이의 사탕 사기

 

---

나:

n = int(input())
a = list(map(int,input().split()))
b = list()
totall = sum(a)


for i in a:
    if i%2 !=0 :
        b.append(i)
if len(b) %2 ==0:
    print(totall)
else:
    b.sort()
    totall = totall - b[0]
    print(totall)

 

완성된 코드는 위와 같다.

 

이 문제는 사탕묶음을 최대한 많이 가져가되 그 총 개수가 홀수가 안되게 만드는 것이다. 

 

그러기 위해서 우선 짝수개를 가진 사탕묶음의 경우는 짝수끼리 더해도 여전히 짝수이기 때문에 그냥 가져가면 된다. 그런데 여기서 고민해야할 부분은 바로 홀수이다. 

 

1. 홀수개의 사탕묶음이 하나만 있는 경우 짝수+ 홀수 =홀수 이지만  홀수개의 사탕묶음이 짝수개의 경우 홀수 + 홀수 =짝수 가 되기 때문에 홀수의 사탕묶음의 개수가 짝수개면 홀수개의 사탕묶음 둘을 짝지어 같이 가져가면 된다.

 

2. 그런데 이때 사탕묶음이 3개 이상의 홀수개의 경우일 때 최대의 사탕의 개수를 가져오기 위해 홀수개의 사탕묶음중 가장 적은수의 사탕묶음을 뺴줘야 한다.

 

이를 구현한 코드 설명은 아래와 같다.

 

 

(1)
n = int(input())
a = list(map(int,input().split()))
b = list()
totall = sum(a)

첫째 줄에는 사탕 묶음의 개수 n 개를 정수형으로 입력받는다.

 

이후 각 묶에 담겨있는 사탕의 개수를 공백을 기준으로 입력받기 위해 list를 이용한 변수 a를  선언.

 

홀수인것들을 담을 리스트 변수 b를 선언.

 

그리고 전체 사탕의 개수를 담은 totall 변수를 선언.

 

(2)
for i in a:
    if i%2 !=0 :
        b.append(i)
        
if len(b) %2 ==0:
    print(totall)
else:
    b.sort()
    totall = totall - b[0]
    print(totall)

 

반복문을 이용해 입력받은 모든 사탕 묶음의 사탕개수가 짝수 혹은 홀수 인지 판단해서 홀수면 앞서 선언했던 b 리스트에 넣는다.

 

그리고 홀수가 들어간 b 리스트에서 만약 그 리스트의 요소 개수가 짝수일 경우 홀수+홀수 = 짝수의 경우로 짝지어서 가져갈 수 있기 때문에 모든 사탕묶음을 가져가면 되서 totall 변수를 그대로 출력한다.

 

만약 b 리스트의 요소 개수가 홀수의 경우 홀수+홀수 =  짝수로 짝을 지어도 홀수 하나가 반드시 남기 때문에 그 홀수를 전체 totall 에서 빼준다.

이때 그 홀수는 홀수들 중에서 가장 작은 값이 되어야 하기 때문에 홀수들의 모임인 b리스트를 오름차순으로 정렬시켜 가장 첫번째 인덱스 0  위치에 존재하는 홀수를 전체에서 뺴준값을 출력시킨다.