오늘의 키워드
•
그리디
•
부분합
문제 파악 및 풀이
•
처음에는 DP나 이분 탐색과 같은 다양한 접근법을 떠올렸지만, 권장 시간인 45분 이내에 풀지 못했다.
•
문제를 아무리 고민해도 해결 방법이 명확히 떠오르지 않아 풀이를 찾아보았고, 그리디 알고리즘으로 접근해야 하는 문제임을 알게 되었다.
•
주어진 추들을 오름차순 정렬한 뒤, 만들 수 있는 무게 범위를 하나씩 확장해나가며 가장 작은 만들 수 없는 무게를 찾는 방식이다.
핵심 아이디어
•
현재까지 만들 수 있는 모든 무게의 합을 sum이라고 할 때,
•
다음 추의 무게가 sum + 1보다 크면, sum + 1 무게는 만들 수 없다.
•
그렇지 않다면, 현재 추를 추가하여 만들 수 있는 무게 범위를 확장한다.
오늘의 회고
어려웠던 점
•
DP, 이분 탐색 등 여러 접근을 시도했지만 그리디 발상을 하지 못했다.
•
문제를 풀면서 계속 방법을 고민했지만, 권장 시간 안에 풀지 못해 아쉬움이 컸다.
개선점
•
그리디 문제는 '현재 최선의 선택'이 전체 최적을 보장하는 조건을 파악하는 연습이 필요하다.
•
비슷한 유형의 그리디 문제를 더 풀어보면서 문제 경험과 그리디 감각을 키워야겠다.