Logo냥냠감자기술 블로그
Skip to Content
작성일: 2024-01-12

문제

백준 12969 - ABC 

  • 난이도: 골드1
  • 알고리즘: DP

코드

#include <iostream> #include <vector> #include <cstring> using namespace std; char cache[30][30][30][30][450]; vector<char> retStr; int strLen; int getRet(int index, int aNum, int bNum, int cNum, int target) { if(index==strLen) { if(target==0) { return 2; } return 1; } if(target<0) { return 1; } char& ret=cache[index][aNum][bNum][cNum][target]; if(ret!=0) { return ret; } if(getRet(index+1, aNum+1, bNum, cNum, target)==2) { retStr.push_back('A'); return ret=2; } if(getRet(index+1, aNum, bNum+1, cNum, target-aNum)==2) { retStr.push_back('B'); return ret=2; } if(getRet(index+1, aNum, bNum, cNum+1, target-aNum-bNum)==2) { retStr.push_back('C'); return ret=2; } return ret=1; } int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int target; cin>>strLen>>target; memset(cache, 0, sizeof(cache)); if(getRet(0, 0, 0, 0, target)==1) { cout<<-1; } else { for(int i=retStr.size()-1; i>=0; i--) { cout<<retStr[i]; } } }

회고

메모이제이션을 적극 활용하여 문제를 해결했다. 이 풀이가 맞는지 모르겠는데 우선 메모리의 크기가 너무 커 메모리 초과를 피하기 위해 char 배열을 사용하였다. 부분 문제의 수가 3억개 이상이기 때문에 시간 초과 가능성이 없진 않지만, 대부분의 부분 문제의 경우 계산을 할 필요가 없다. 예를 들어 문자열의 길이가 10일 경우 A의 개수, B의 개수, C의 개수의 합이 10 이하인 경우만 부분문제로 계산을 하게 된다. 이런 요소들을 고려했을 때 충분히 시간 안에 돌 것이라 판단하여 위와 같이 코드를 작성했다.