문제
(주의: 이 문제는 TopCoder 의 번역 문제입니다.)
가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.
이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:
모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
그 외의 경우 난이도: 10
원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.
출력
각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.
오답코드
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
string num;
int cache[10001];
int nan2do(int start, int end)
{
string tmp;
for(int i = start; i<end; i++)
tmp.push_back(num[i]);
bool check = true;
//////////////////
for(int i = 0; i<tmp.size(); i++)
if(tmp[i]!=num[i]) check = false;
if(!check) return 1;
check = true;
//////////////////
int diff = tmp[1] - tmp[0];
for(int i = 0; i<tmp.size()-1; i++)
if(tmp[i+1]-tmp[i] != diff) check = false;
if( (diff==1 && check) || (diff==-1 && check)) return 2;
////////////////////
bool check4 = true;
for(int i = 0; i< tmp.size()-2; i++)
{
if(tmp[i] != tmp[i+2]) check4 = false;
}
if(check4) return 4;
if(check) return 5;
return 10;
}
int memorize(int begin)
{
if(begin == num.size()) return 0;
int& ret = cache[begin];
if(ret != -1) return ret;
ret = 987654321;
for(int L = 3; L <= 5; L++)
{
if(begin + L <= num.size())
ret = min(ret, memorize(begin + L) + nan2do(begin, begin + L -1));
}
return ret;
}
int main()
{
FASTio;
int t;
cin >> t;
while(t--)
{
memset(cache, -1, sizeof(cache));
cin >> num;
cout << memorize(0) << endl;
}
return 0;
}정답코드
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
const int INF = 987654321;
string N;
int cache[10002];
int levelPI(int a,int b)
{
string M = N.substr(a, b-a + 1);
if (M == string(M.size(), M[0])) return 1;
bool progressive = true;
for (int i = 0; i < M.size() - 1; i++)
if (M[i + 1] - M[i] != M[1] - M[0])
progressive = false;
if (progressive &&abs(M[1] - M[0]) == 1)
return 2;
bool alternating = true;
for (int i = 0; i < M.size(); i++)
if (M[i] != M[i % 2])
alternating = false;
if (alternating) return 4;
if (progressive) 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) + levelPI(begin, begin + L - 1));
return ret;
}
int main()
{
FASTio;
int t;
cin >> t;
while(t--)
{
memset(cache, -1, sizeof(cache));
cin >> N;
cout << memorize(0) << endl;
}
return 0;
}풀이 및 사고과정
난이도를 찾는 과정은 아이디어가 있어서 스스로 작성했지만 DP에 대한 아이디어는 쉽게 떠오르지 않았다. 그래서 책에 있는 아이디어를 보고 약간의 수정을 거쳐 TC를 넣어봤지만 이미 작성했던 난이도에 대한 함수가 오류가 있었다.
난이도에 나온 아이디어는 책에 것과 나의 아이디어가 비슷했다. 일단 이것은 만족하지만 DP에 대한 사고는 연습해야될 것 같다.
오답코드는 추후에 손을 봐서 돌아가게 만들어봐야겠다.
good