728x90

문제

(주의: 이 문제는 TopCoder 의 번역 문제입니다.)

가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

  1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1

  2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2

  3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4

  4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5

  5. 그 외의 경우 난이도: 10

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.

 

출력

각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.


문자열의 시작 위치부터 차례대로 조사한다. 글자 길이가 3~5글자 일 때만 점수를 낼 수 있으므로 현재 위치 start + i 일때 점수와 그 이후까지의 점수 중 최소값을 조사해서 현재 값보다 작을 때만 저장하면 된다. 재귀를 통해 최소값을 반환하는 pi 함수와 3~5글자를 잘라서 점수를 세는 score 함수를 이용한다. score함수 자체는 문제의 조건을 따라 작성하기만 하면 된다. 이 떄 반환 순서는 작은 값부터 return해야 더 큰 점수로 반환하는 오류를 범하지 않게 된다.

 

 

코드 원본 :  https://github.com/chosh95/STUDY/blob/master/Algospot/PI.cpp

 

chosh95/STUDY

알고리즘 문제풀이. Contribute to chosh95/STUDY development by creating an account on GitHub.

github.com

C++ 코드 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int C, len;
string str;
int dp[10003];
int score(int start, int end)
{
	bool tmp = true;
	for (int i = start+1; i <= end; i++) {
		if (str[i] != str[i - 1]) {
			tmp = false;
			break;
		}
	}
	if (tmp) return 1;

	tmp = true;
	for (int i = start + 1; i <= end; i++) {
		if (str[i] - 1 != str[i - 1]) {
			tmp = false;
			break;
		}
	}
	if (tmp) return 2;
	tmp = true;
	for (int i = start + 1; i <= end; i++) {
		if (str[i] + 1 != str[i - 1]) {
			tmp = false;
			break;
		}
	}
	if (tmp) return 2;

	tmp = true;
	for (int i = start + 2; i <= end; i++) {
		if (str[i] != str[i - 2]) {
			tmp = false;
			break;
		}
	}
	if (tmp) return 4;

	tmp = true;
	for (int i = start + 1; i <= end; i++) {
		if (str[i] - str[i - 1] != str[start + 1] - str[start]) {
			tmp = false;
			break;
		}
	}
	if (tmp) return 5;
	return 10;
}
int pi(int start)
{
	if (start == len) return 0;
	int& res = dp[start];
	if (res != -1) return res;
	res = 987654321;
	for (int i = 3; i < 6; i++) {
		if (start + i <= len) {
			res = min(res, pi(start + i) + score(start, start + i - 1));
		}
	}
	return res;
}

int main()
{
	cin >> C;
	while (C--) {
		cin >> str;
		len = str.size();
		memset(dp, -1, sizeof(dp));
		cout << pi(0) << endl;
	}
}
728x90

+ Recent posts