예제: 원주율 외우기
문제
(주의: 이 문제는 TopCoder 의 번역 문제입니다.)가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.
이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:
모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
그 외의 경우 난이도: 10
원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.출력
각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.예제 입력
5 12341234 11111222 12122222 22222222 12673939예제 출력
4 2 5 2 14
풀이
동적 계획법 문제이다.
난이도 구하는 함수를 작성하는 것이 귀찮고 어렵고 버그의 가능성이 많은 것 같다.
난이도 구하는 함수만 제대로 구현했다면, 나머진 크게 어렵지는 않았던 문제이다.
사실 필자는 예전에 풀었던 문제인데, 이번에 다시 풀어보면서 numeric_limits를 또 써먹어 보겠다고(...) INF를 구하는데에 썼다가 삽질을 좀 했다.
numeric_limits<int>::max() 인 값에 1이라도 더해지면 어떻게 될까? 그렇다. 음수값이 나온다.
어차피 입력이 10000글자 이하이기 때문에 난이도가 아무리 높아봤자 3333 * 10 이하이다. 걱정말고 INF = 987654321을 써 주면 된다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
//const int& INF = numeric_limits<int>::max();
const int& INF = 987654321;
int cache[10000];
string nums;
int difficulty(int start, int end) {
int res = 10;
bool check;
//난이도 1 : 모든 숫자가 같을 때
check = true;
for (int i = start; i < end; i++) {
if (nums[i] != nums[i + 1]) {
check = false;
break;
}
}
if (check) return 1;
//난이도 2 : 숫자가 1씩 단조 증가하거나 단조 감소할 때
check = true;
for (int i = start; i < end - 1; i++) {
int prev = nums[i] - nums[i + 1], next = nums[i + 1] - nums[i + 2];
if (abs(prev) != 1 || prev != next) {
check = false;
break;
}
}
if (check) return 2;
//난이도 4 : 두 개의 숫자가 번갈아가며 나타날 때
check = true;
for (int i = start; i < end - 1; i++) {
if (nums[i] != nums[i + 2]) {
check = false;
break;
}
}
if (check) return 4;
//난이도 5 : 이 숫자가 등차 수열을 이룰 때
check = true;
for (int i = start; i < end - 1; i++) {
if ((nums[i] - nums[i + 1]) != (nums[i + 1] - nums[i + 2])) {
check = false;
break;
}
}
if (check) return 5;
return res;
}
int easist(int idx) {
int size = nums.size();
if (idx == size) return 0;
if (idx + 2 >= size) return INF;
int& res = cache[idx];
if (res != -1) return res;
res = INF;
for (int i = 2; i <= 4; i++) {
//res = min(res, difficulty(idx, idx + i) + easist(idx + i + 1) >= 0
? difficulty(idx, idx + i) + easist(idx + i + 1) : INF);
res = min(res, difficulty(idx, idx + i) + easist(idx + i + 1));
}
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
memset(cache, -1, sizeof(cache));
cin >> nums;
cout << easist(0) << endl;
}
return 0;
}풀이 후기
요즘은 왜이렇게 한번에 풀질 못하는지 모르겠다.
집중력이 떨어져서인지, 배가고파서인지, 야근하고 와서인지 모르겠다.
홍삼하나 먹고 힘내자! 으쌰으쌰🤗
