#include <iostream> #include <algorithm> #include <cstring> #define INF 987654321; using namespace std; int t; string n; int cache[10002]; int classify(int a, int b) { // 숫자 조각을 가져옴 string m = n.substr(a, b-a+1); // 난이도 1 검사 - 모두 같은 수 if(m == string(m.size(), m[0])) return 1; // 난이도 2 검사 - 등차수열이자 공차가 1 or -1 bool prog = true; for(int i=0;i<m.size()-1;i++) if(m[i+1] - m[i] != m[1] - m[0]) prog = false; if(prog && abs(m[1] - m[0]) == 1) return 2; // 난이도 4 검사 - 두 수 번갈아가면서 bool alter = true; for(int i=0;i<m.size();i++) if(m[i] != m[i%2]) alter = false; if(alter) return 4; // 난이도 5 검사 - 등차수열 if(prog) return 5; // 이외 return 10; } int memorize(int begin) { if(begin == n.size()) return 0; int &ret = cache[begin]; if(ret != -1) return ret; ret = INF; for(int L=3;L<=5;L++) { if(begin + L <= n.size()) ret = min(ret, memorize(begin + L) + classify(begin, begin + L - 1)); } return ret; } int main() { // cin.tie(NULL); ios::sync_with_stdio(false); cin >> t; while(t--) { memset(cache, -1, sizeof(cache)); cin >> n; cout << memorize(0) << "\n"; } }
문자열을 3조각 이상 5조각 이내로 쪼갤 때 만들 수 있는 최소 난이도를 구하는 문제입니다.
난이도를 검사해주는 classify 함수와 난이도의 조합을 메모이제이션으로 구현한 memorize 함수를 이용했습니다.
꽤 재미있었던 문제였습니다. 하단의 책을 참고하여 코드를 작성하였습니다.
[출처] 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만
'Algorithm > Baekjoon & Algospot' 카테고리의 다른 글
[C++] BOJ 6118 - 숨바꼭질 (0) | 2018.07.27 |
---|---|
[C++] BOJ 1309 - 동물원 (0) | 2018.07.23 |
[C++] BOJ 1012 - 유기농 배추 (0) | 2018.07.17 |
[C++] BOJ 7785 - 회사에 있는 사람 (0) | 2018.07.16 |
[C++] BOJ 13016 - 내 왼손에는 흑염룡이 잠들어 있다 (0) | 2018.07.15 |