알고리즘 문제해결 전략 Chapter 08 - PI(C++)

포타토·2020년 1월 6일
0

알고리즘

목록 보기
20/76

예제: 원주율 외우기

문제
(주의: 이 문제는 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;
}

풀이 후기

요즘은 왜이렇게 한번에 풀질 못하는지 모르겠다.
집중력이 떨어져서인지, 배가고파서인지, 야근하고 와서인지 모르겠다.
홍삼하나 먹고 힘내자! 으쌰으쌰🤗

profile
개발자 성장일기

0개의 댓글