[백준] 2+1 세일 : 11508번 - Python

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

11508번: 2+1 세일

 

 

 

문제를 풀면서 몰랐던 개념

 

(1) 일정 부분 합 구하기

-> sum 메소드와 슬라이싱 사용!!!

arr = [10, 20, 30, 40, 50]

a = sum(arr[:2])
b = sum(arr[:3])
print(a)
print(b)

>> 30
>> 60

* sum 메소드는 합을 구해준다

 

(2) 리스트를 특정 크기의 리스트로 분할하기

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

n = 4	# 4개씩 분리하기

result = [arr[i*n:(i+1)*n] for i in range((len(arr)-1+n) // n )]
print(result)

>> [[1, 2, 3, 4], [5, 6, 7, 8], [9]]

* result의 리스트 컴프리헨션에 대한 해설

: 9개를 4개씩 나누면 각각 4,4,1개가 들어가는 세 개의 리스트로 나누어진다.

이것은 ((9-1)//4)+1 과 같음.

(len(arr)-1//n)+1  ---> (len(arr)-1+n)//n)

이것은 곧 3이다! 따라서 3개의 리스트가 들어있는 결과물이 나오게 됨.

 

또, result = [arr[0:4], arr[4:8], arr[8:12]]가 돼서 출력이 됨.

 

 

 

문제의 접근 방법

 

* 내가 처음에 생각했던 방식 *

내림차순 정렬 후 가장 큰 값만 빼낸 후, 다시 남은 원소들을 오름차순 정렬

ex) 10, 9, 4, 2, 6, 4, 3 -> 10, 9, 6, 4, 4, 3, 2 -> 10(최댓값)만 빼내서 저장 -> 9, 6, 4, 4, 3, 2 -> 남은 원소들 오름차순으로 정렬 -> 2, 3, 4, 4, 6, 9 -> 10을 저장해둔 리스트에 나머지 원소들 추가 -> 10, 2, 3, 4, 4, 6, 9

이 순서대로 3개씩 잘라서 저장하기 => 최소비용을 구할 수 있음!

 

 

 

내가 막혔던 부분

 

- 리스트를 3개의 원소씩 잘라서 출력하는 방법

- 최소 비용이 나올 수 있는 숫자들의 규칙 찾기

 

 

 

 

문제 풀이 방법

 

(1) n개의 유제품 n값 입력 받기

(2) n번만큼 반복문을 돌려 n개의 유제품들의 가격을 줄 단위로 입력받고, 미리 선언해 둔 리스트 arr에 추가

(3) 리스트 arr를 내림차순으로 정렬

(4) 리스트 arr에 저장되어있는 원소들을 3개씩 잘라서 리스트에 저장

(5) 2차원 배열이기 때문에 i번째 행의 두 번째 원소까지 더한 값을 변수 s에 누적해서 더하기 (원소가 3개든, 2개든, 1개든 앞에서 두 번째 값까지만 비용 계산에 포함되기 때문)

(6) 더해진 최소 비용(합계) s 출력

 

 

 

다른 풀이 방법

 

내림차순으로 정렬한 후 3의 배수 자리의 숫자를 없애준다 -> 남은 값들을 다 더해준다!

ex) 6 6 4 5 5 5 5

[6 5 5 5 5 4]

6+5(5제외) + 5+5(5제외) = 21

 

=> 이렇게 하면 제외되는 값이 가장 큰 값이 되기 때문에 최솟값을 도출해낼 수 있다...!!!!!

 

 

 

소스코드

n = int(input())

arr = []

for _ in range(n):
    price = int(input())
    arr.append(price)
arr.sort(reverse=True)

n = 3
result = [arr[i*n:(i+1)*n] for i in range((len(arr)+n-1)//n)]

s = 0
for i in range(len(result)):
    s += sum(result[i][:2])

print(s)