[종만북 문제] 원주율 외우기 (문제 ID : PI, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 원주율 같은거 좀 외우고 다니지 말자;

---

[종만북 문제] 원주율 외우기 (문제 ID : PI, 난이도 : 하)

문제 자체는 어렵지 않다! 그냥 점화식만 잘 세우면 되는데... 일단 코드를 보자.

#include <iostream>
#include "stdlib.h"
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

int N;
vector<int> arr;
vector<int> cache;

int diff(int i, int j)
{
	if (i > j)
		return 0;

	if (j >= N)
		return 10;

	if ((j - i > 1) && (j - i < 5))
	{
		// 1. all numbers are equal
		bool fit = true;

		for (int idx = i; idx < j; ++idx)
		{
			if (arr[idx] != arr[idx + 1])
			{
				fit = false;
				break;
			}
		}
		if (fit)
			return 1;

		// 2. increasing / decreasing at rate of 1
		fit = true;
		for (int idx = i; idx < j; ++idx)
		{
			if (arr[idx] + 1 != arr[idx + 1])
			{
				fit = false;
				break;
			}
		}
		if (fit)
			return 2;

		fit = true;
		for (int idx = i; idx < j; ++idx)
		{
			if (arr[idx] - 1 != arr[idx + 1])
			{
				fit = false;
				break;
			}
		}
		if (fit)
			return 2;


		// 3. two numbers are alternating
		fit = true;
		for (int idx = i; idx < j; ++idx)
		{
			if (idx + 2 <= j)
			{
				if (arr[idx] != arr[idx + 2])
				{
					fit = false;
					break;
				}
			}
		}
		if (fit)
			return 4;


		// 4. increasing/decreasing same rate
		fit = true;
		int dif = arr[i+1] - arr[i];
		for (int idx = i; idx < j; ++idx)
		{
			if (arr[idx + 1] - arr[idx] != dif)
			{
				fit = false;
				break;
			}
		}
		if (fit)
			return 5;
	}

	// 5. other
	return 10;
}

int sol(int idx)
{
	if (idx >= N)
		return 0;

	if (cache[idx] != numeric_limits<int>::max())
		return cache[idx];

	int& ret = cache[idx];

	for (int i = 2; i < 5; ++i)
	{
		ret = min(ret, diff(idx, idx + i) + sol(idx + i + 1));
	}

	return ret;
}

void inputHandler()
{
	arr.clear();
	cache.clear();

	string nums;
	cin >> nums;

	N = nums.size();

	for (int i = 0; i < N; ++i)
		arr.push_back(nums[i] - '0');

	cache.resize(N, numeric_limits<int>::max());
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		cout << sol(0) << endl;
	}
	return 0;
}

 

책에서는 간단한 점화식을 세우면 된다고 나와 있다.

사실 위의 설명이면 이제 끝난건데... 다만 책의 구현을 보니, 패턴을 검사하는 코드가 아주 간결해서 가져와봤다. 😆