[백준 알고리즘] 1026번: 보물 (Python)

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

1026번: 보물

알고리즘을 알지 못해도 풀 수 있는 문제라고 생각하지만, 백준 사이트의 알로리즘 분류에는 '그리디 알고리즘'으로 분류되어 있습니다. 

 

그리디 알고리즘이란 매 순간 최적의 선택을 하여 문제를 풀어나가는 기법입니다.

 

소스 코드

 

풀이 

파이썬에는 다른 언어들과 다르게 다양한 함수를 활용할 수 있습니다. 

이 문제에서는 remove(), min(), max() 함수를 활용하였습니다. 

 

min() 함수는 배열에서 최솟값을 찾아주며, max() 함수는 최댓값을 찾아줍니다. 

또한 remove() 함수는 배열에서 특정 값을 삭제할 때 사용할 수 있는 함수입니다. 

 

문제에 나와있는 예제들을 보면, 배열 a의 최솟값과 배열 b의 최댓값을 곱한 뒤 그 값들을 더했을 경우에 S의 최솟값이 나온다는 것을 알 수 있습니다. 

 

이를 위해 ,

주어진 n만큼 반복문을 돌며, 배열 a에서 최솟값을 찾고, 배열 b에서는 최댓값을 찾아 곱한 값을 s에 누적시켜줍니다.

이때, 이미 한번 곱한 값은 배열에서 삭제되어야 하기에 remove 함수를 통해 삭제시킵니다.