2022 알고리즘 탐구반 #8

계획

월요일마다 교내대회때문에 빠지면서 동아리 활동시간을 못 채울 것 같아서 점심시간에 하기로 했다.

사실 동아리는 1학년 한명, 2학년 한명 두고 하는건데 1학년 애가 점심시간에 수행이 있다고 해서 동아리를 제대로 못하겠다는 생각이 들었다. 시간도 짧기도 하고.

그래서 그냥 DP와 그리디 문제 하나씩 넣어놨다.

DP는 차원이 높아질 수도 있다는 것을 보여주기 위해 '건포도'로 선택했고, 그리디는 그리디와 DP를 구분할 수 있는지 테스트하기 위해 거스름돈을 주기위한 최소의 동전개수를 구하는 문제이지만 동전이 배수관계로 주어지는 문제를 선택했다.

---

결과

시간이 30분정도밖에 안돼서 그냥 문제 풀이 생각까지만 하기로 했다.

그리디 문제는 쉽게 방법을 떠올려서 건포도만 잡고 있었는데, DP인듯한 감은 오지만 어떻게 식을 세워야할지 모르겠다고 해서 힌트를 조금 던져줬다.

월요일에 시간 조금 더 주고 풀이하기로 했다.

아직 DP가 익숙하진 않은 것 같아서 조금 더 쉬운 DP문제를 몇개 추가해야겠다.