Awesome

첫째 줄은 막대기의 길이이다.

둘째 줄은 각 막대기의 가격이다.

한 막대기를 선택해서, 그 막대기를 적절하게 자르든 안 하든, 가장 비싼 가격을 만들어야 한다.

예를 들어 길이 4의 막대기는 2로 나누어서 5+5=10이 최대 가격이 된다.

막대기 n을 선택해 나누려고 하는데,

i를 1부터 시작해서 i : n-i 비율로 나눴다고 생각하자. 

예를 들어 막대기 4를 1:3, 2:2, 3:1, 4:0 비율로 나눌 수 있다. 

이 때 i는 1부터 n까지 모든 경우를 볼 것이기 때문에 더이상 건들지 말고 표 가격 그대로라고 생각하고,

n-i의 가격을 최대 가격이라고 생각하면

i=n까지 계산 및 비교를 끝냈을 때 n의 최대 가격을 알아낼 수 있을 것이다.

4를 1:3으로 나눴다면 1을 기준점으로 삼고 그냥 두고, 3을 막대기 3의 최대 길이라고 생각하자는 것이다.

이것을 점화식으로 나타내면 다음과 같다.

Rn = max(Pi + Rn-i) (i=1~n. R은 최대 가격, P는 표에 주어진 가격)

R1 = max(P1 + R0)

R2 = max(P1 + R1, P2 + R0)

R3 = max(P1 + R2, P2 + R1, P3 + R0)

R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0)

....

계속해서 R0, R1, R2 등의 계산이 반복되고 있기 때문에 동적 프로그래밍으로 풀어갈 수 있다.

다이나믹 프로그래밍은 점화식을 알아내면 풀 수 있다고 한다. 

저 문제를 봤을 때 DP인 것을 인식하고 수식을 생각해낼 수 있을지 솔직히 지금은 자신없지만...

동전 문제는 그리디 알고리즘이 되는 이유가

예를 들어 화폐가 500원, 100원 두 가지라면 500과 100의 최소공배수가 더 작은 수(100)이기 때문이라고 한다.

100x5=500으로 표현 가능하지만 이러할 경우 500으로 표현하는 것이 유리하기 때문에,

내림차순으로 정렬한 후에 그리디 알고리즘으로 해결 가능하다는 것 같다.

만약 화폐가 500원, 400원이라면 500은 400의 자연수 배수로 표현할 수 없기 때문에 그리디 알고리즘으로 풀 수 없다고 한다.

answer = 0

price = int(input())
change = 1000 - price
bank = [500, 100, 50, 10, 5, 1]

for coin in bank:
    if change >= coin:
        answer += change // coin
        change %= coin
        if change == 0:
            break

print(answer)

분명 문제가 그리디 카테고리에 있었지만 처음엔 완전탐색으로 풀었던 것 같다.

0부터 시작해 가능한 경우를 다 세보면서, 최대 회의 수를 max로 두고 마지막 max를 출력하는 방식으로 풀었다.

그렇게 하니 예시에 대한 답은 맞췄지만 채점 중 시간초과가 나왔다.

결국 구글링으로 힌트를 찾았다.

포인트는 회의가 끝나는 시간을 기준으로 정렬한 후에 그리디로 푸는 것.

회의가 끝나는 시간을 기준으로 삼으면, 앞으로 회의를 진행할 수 있는 남은 시간이 많이 남기 때문이라는 것이다.

만약 이 문제 유형이 그리디라는 것을 몰랐다면, 그리디로 풀어낼 수 있었을까?

생각하지 못했을 것 같다.

아직 처음이니까, 풀다보면 감이 오겠지.

answer = 0

n = int(input())
timeTable = []
for i in range(n):
    timeTable.append(tuple(map(int, input().split())))
timeTable.sort(key=lambda t: (t[1], t[0]))

last = 0
for t in timeTable:
    if t[0] >= last:
        answer += 1
        last = t[1]

print(answer)