Logo냥냠감자기술 블로그
Skip to Content
AlgorithmBruteforce (11)망가진 계산기
작성일: 2024-01-12

문제

백준 1443 - 망가진 계산기 

  • 난이도: 골드1
  • 알고리즘: 브루트포스

코드

#include <iostream> #include <vector> #include <string> using namespace std; int availShow, calNum; int calReturn(vector<int>& countPerNum) { int ret=1; for(int i=2; i<10; i++) { for(int j=0; j<countPerNum[i]; j++) { ret*=i; string retToString=to_string(ret); if(retToString.size()>availShow) { return -1; } } } return ret; } int getMax(int currNum, vector<int>& countPerNum, int remain) { if(currNum==10) { return calReturn(countPerNum); } else if(currNum==9) { countPerNum[currNum]=remain; int ret=getMax(currNum+1, countPerNum, 0); countPerNum[currNum]=0; return ret; } int ret=-1; for(int i=remain; i>=0; i--) { countPerNum[currNum]=i; int currMax=getMax(currNum+1, countPerNum, remain-i); countPerNum[currNum]=0; if(currMax==-1) { break; } ret=max(ret, currMax); } return ret; } int main() { cin>>availShow>>calNum; vector<int> countPerNum(10, 0); cout<<getMax(2, countPerNum, calNum); }

회고

문제를 풀었는데 레이팅이 내려갔다…왜지…지금까지 푼 문제 중 난이도가 변한 문제가 있는 모양이다. 아이디어 자체는 어렵지 않았자민, 최적화가 필요했다.