백준 1049 파이썬(그리디)

그리디 문제로 발생할 수 있는 경우의 수를 차근차근 따져보면서 풀어보면 된다.

 

우선 이 문제는 사야하는 줄보다 더 많이 사도 된다는 것이 포인트이다.

그래서 6개 세트로 넉넉하게 살 경우 1개를 낱개로 맞춰서 사는 경우보다 저렴할 경우 넉넉하게 사도 된다.

또 놓치지 말아야 할 부분은 6개 세트가 낱개로 6개를 살때보다 항상 싸다는 말은 없다. 따라서 이 부분도 신경을 써주어야 한다. 

이를 코드로 표현하면 아래와 같다. 

 

# 1049번 기타줄

n,m = map(int,input().split())
line_set = []
line_ = []
for i in range(m):
    a,b = map(int,input().split())
    line_set.append(a)
    line_.append(b)

e = min(line_set)
f = min(line_)

if e < f*6:
    share = n // 6 # 몫
    remain = n % 6 # 나머지
    print(share*min(line_set) + min(min(line_set),remain*min(line_)))
else:
    print(n*f)

---

Greedy

[정의]

• 발견법(heuristic method)중 하나이다. - 인간의 '감', '어림짐작'등 인간의 경험적인 부분을 알고리즘으로 표현한 것이다.
• 주어진 상황을 한단계씩 빠른 시간 내에 해결하기
• 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.
• 단, 그 순간에는 최적의 선택이지만 종합적으로 봤을 땐 최적이 아닐수도 있다. (ex. 조삼모사)

---

[조건]
1.탐욕스러운 선택 조건(Greedy choice property) - 문제해결관점
2.최적 부분 구조 조건(Optimal Substructure) - 문제 구조관점

• <탐욕스러운 선택 조건 (Greedy choice property)>
  앞의 선택이 이후의 선택에 영향을 주지 않는 조건.
• <최적 부분 구조 조건(Optimal Substructure)>
  문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다는 조건.

---

[greedy vs DP]

• 그리디 - 최적부분구조 + 탐욕스러운 서브조건 (서브문제 중복X)
• DP - 최적부분구조 + 중복되는 서브문제