나를 잃지 말자

문제:https://www.acmicpc.net/problem/1931

비고:

-Greedy algorithm 활용(Optimal substructure, Greedy choice property)

-list.sort(key=lambda x: (x[1],x[0])) 형태로 주면, multiple fields에 대해 우선순위 줘가며 sorting이 가능

-다음 케이스를 놓쳐서 오래 걸림

5

4 4

4 4

3 4 

2 4 

1 4

정답은 3

-즉 포인트는 같은 종료 시간 내에 시작 시간을 정렬해야 한다는 점과 그 때 단순히 이어진 시작 시간 2개 교체해나가는 바람에 100%에서도 틀렸습니다를 얻게됨

-생각보다 오래걸림 ㅠㅠ

-난이도가 중

내소스코드:

boj.kr/d38992bbf196403e87c8619016a051c2

문제:https://www.acmicpc.net/problem/12845

비고:

-Greedy algorithm 문제가 뭐 없나 찾아보던 중 발견했는데, 너무 쉬운 문제

-Greedy를 떠나서, 잘 살펴보면 결국 max값이 (N-1)번 더해지고, 남은 것들을 더해주기만 하면 된다.

-따라서 Subproblem을 떠나서 Explicit solution을 구해버릴 수가 있음

-난이도가 낮음

내소스코드:

boj.kr/2d49ff4b4e924b0693a2574534588dd4

문제:https://www.acmicpc.net/problem/11047

비고:

-Greedy algorithm 활용(Optimal substructure, Greedy choice property)

-python3, divmod를 통해 몫과 나머지를 바로 구함

-난이도가 낮음

내소스코드:

boj.kr/d957b77f0a804e328ac66afd615ac0c6