Logo냥냠감자기술 블로그
Skip to Content
AlgorithmDP (31)수 이어가기
작성일: 2024-01-15

문제

백준 14916 - 수 이어가기 

  • 난이도: 실버5
  • 알고리즘: dp

코드

#include <iostream> #include <vector> using namespace std; int MAXCOIN=987654321; vector<int> cache(100001, MAXCOIN); int getCoinNum(int money) { if(money<0) return MAXCOIN; if(money==0) return 0; if(cache[money]!=MAXCOIN) return cache[money]; cache[money]=min(getCoinNum(money-2), getCoinNum(money-5))+1; return cache[money]; } int main() { int money; cin>>money; int ret=getCoinNum(money); ret<MAXCOIN ? cout<<ret : cout<<-1; }

회고

스터디 하면서 푼 문제이다. 평소처럼 cache를 -1로 초기화 하고 싶었는데, 최소 값을 구하는 로직 상 -1일때 예외 처리를 해주기 귀찮아서 그냥 아주 큰 값을 대입했다.
수민 누나가 그리디로 풀었는데 조금 신기한 방법이었다. 문제를 습관적으로 풀지 말고 여러 방법을 생각해 봐야겠다.
맥북에서 백틱 위치를 누르면 한글이면 ₩, 영어면 백틱이 출력된다. 따라서 vscode 터미널을 열고 싶으면 영문 타자 상태에서 ctrl+백틱을 입력해야 한다.