백준 10942번 _ 팰린드롬?

2020-05-05 · 배운 것 · 3분 읽기

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

풀이방법

https://blog.fxjodo.com/blog/60/

프로그래머스_가장 긴 팰린드롬

이 문제와 유사하다. 자세한 설명은 위에 해놨으니 참고하기 바란다.

전체코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool palindrome[2001][2001];
vector<pair<int, int>>orders;
int arr[2001];
int N, M;

void Input()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	cin >> M;
	int s, e;
	for (int i = 0; i < M; i++)
	{
		cin >> s >> e;
		orders.push_back({ s, e });
	}
}

void makePalindrome()
{
	//자기 자신은 팰린드롬이다.
	for (int i = 1; i <= N; i++)
		palindrome[i][i] = true;

	//연속된 수도 팰린드롬이다.
	for (int i = 1; i < N; i++)
		if (arr[i] == arr[i + 1])
			palindrome[i][i + 1] = true;

	//팰린드롬 구하기
	for (int gap = 2; gap < N; gap++)
	{
		for (int start = 1; start + gap <= N; start++)
		{
			int  end = start + gap;

			if (arr[start] == arr[end])
			{
				if (palindrome[start + 1][end - 1] == true)
					palindrome[start][end] = true;
			}
		}
	}
}

void solve()
{
	for (auto& order : orders)
	{
		int start = order.first;
		int end = order.second;

		if (palindrome[start][end] == true)
			cout << 1 << '\n';
		else
			cout << 0 << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	Input();
	makePalindrome();
	solve();
	return 0;
}

시간

0.5초가 주어진다. 약 5000만번의 연산이다. 그리고 n은 최대 2000이므로 대충연산을 계산해보면
자기자신 (n번) + 연속된 수(n번) + 팰린드롬구하기 (n^2)이므로 시간은 충분하다.

시간복잡도는 O(n^2)이라고 할수있다.

후기

팰린드롬 배열을 구할때 다해놓고 값을 안넣는 만행을 저지르는 바람에 몇번 틀린문제다.
역시 아직 난 하수다.