백준 - 1026번 보물 python 문제풀이 [Hellfer]

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

1026번: 보물

🔷 알고리즘 분류 - 그리디 알고리즘, 난이도 - 실버 4

그리디 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 결정을 하는 방식으로 문제를 해결하는 알고리즘입니다. 

 

이 때문에 그리디 알고리즘은 '탐욕적'이라는 뜻의 '그리디'라는 이름이 붙었습니다. 

 

그리디 알고리즘이 작동하는 기본 원리는 간단합니다. 

 

매 순간 최선의 선택을 하면서 전체 문제의 해결책을 찾아나갑니다. 

 

이 때문에 그리디 알고리즘은 많은 종류의 최적화 문제에 효율적으로 사용될 수 있습니다. 

 

그러나 그리디 알고리즘은 '항상 최적의 해결책을 보장하는가?'라는 중요한 질문에 대한 답이 '아니요'일 수 있다는 점에서 주의할 필요가 있습니다. 

 

그리디 알고리즘은 그 자체로 국소적인 최적해를 찾는 데는 탁월하지만, 이가 반드시 전체적인 최적해를 보장하진 않습니다.

🔶문제 풀이 - 그리디 알고리즘을 이용한 풀이

# 입력받은 정수 n을 변수 n에 저장합니다.
n=int(input())

# 공백으로 구분된 정수들을 입력받아 리스트로 변환하고, 이를 x에 저장합니다.
x=list(map(int,input().split()))

# 공백으로 구분된 정수들을 입력받아 리스트로 변환하고, 이를 y에 저장합니다.
y=list(map(int,input().split()))

# 빈 리스트 result를 생성합니다. 이 리스트는 x와 y의 각 원소를 곱한 값을 저장할 것입니다.
result=[]

# x를 오름차순으로 정렬합니다.
x.sort()

# y를 내림차순으로 정렬합니다.
y.sort(reverse=True)

# n번 반복하는 for loop를 실행합니다.
for i in range(n):
    # x와 y의 i번째 원소를 곱한 값을 result에 추가합니다.
    result.append(x[i]*y[i])
    
# result의 모든 원소의 합을 출력합니다.
print(sum(result))

🔶 초보자를 위한 해결전략

1. 문제 이해: 이 문제는 두 개의 정수 배열 A와 B가 주어졌을 때, 각각의 i번째 원소 A [i]*B [i]의 값을 모두 더하여 결괏값이 최소가 되도록 하는 문제입니다. 배열 A의 원소들은 재배열이 가능하지만, 배열 B는 재배열이 불가능합니다.

2. 문제 분석: 배열 A의 원소들을 재배열하여 A [i]*B [i]의 총합이 최소가 되도록 해야 합니다. 이는 배열 A의 최솟값과 배열 B의 최댓값을 곱하면 최소가 되는 원리를 이용합니다.

3. 해결 전략 선택: 그리디 알고리즘을 선택합니다. 이 문제에서 가장 최적의 선택은 '배열 A의 최솟값과 배열 B의 최댓값을 곱하고, 이 과정을 반복'하는 것입니다.

4. 알고리즘 설계: 먼저, 배열 A를 오름차순으로 정렬하고, 배열 B를 내림차순으로 정렬합니다. 그리고 각 인덱스에 대해 배열 A와 B의 원소를 곱한 값을 더합니다.

이러한 단계를 거쳐 문제를 해결할 수 있습니다. 이 문제의 경우 그리디 알고리즘이 가장 효율적인 해결 방법이므로, 이를 이용하여 문제를 접근하는 것이 좋습니다.

 

🤗파이팅입니다~ 여러분!!🤗