[Algorithm] 24. Jolly Jumpers

나...난가?...

인트로

재밌는 문제라고 생각해서 기록하려 한다.

Jolly Jumper를 구하는 문제이다. Jolly Jumper의 정의는 다음과 같다.

Jolly Jumper :
N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을 모두 가지는 수열

Jolly Jumper

문제

N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을 모두 가지면 그 수열을 유쾌한 점퍼(jolly jumper)라고 부른다.
예를 들어 다음과 같은 수열에 서 1 4 2 3 앞 뒤에 있는 숫자 차의 절대 값이 각각 3 ,2, 1이므로 이 수열은 유쾌한 점퍼가 된다.
어떤 수열이 유쾌한 점퍼인지 판단할 수 있는 프로그램을 작성하라.

※ 입력설명
첫 번째 줄에 자연수 N(3<=N<=100)이 주어진다.
그다음 줄에 N개의 정수가 주어진다.
정수의 크기는 int 형 범위 안에 있으며, 인접한 두 수의 차도 정수형 범위에 있습니다.

※ 출력설명
유쾌한 점퍼이면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력한다.

입력

5
1 4 2 3 7

출력

YES

코드 설명

이런 유형의 문제를 보면 가장 먼저 bool형 배열(벡터)이 떠오른다.

인접한 수의 차를 저장하고 값을 체크하기에 배열만 한 것이 없다.

 

Jolly Jumpers가 아닌 Case :

[1] 인접한 수의 차가 1 ~ N-1을 벗어난다.

[2] 인접한 수의 차가 중복해서 계산된다.

 

해당 상황을 유의해서 코드를 짜면 쉽게 해결할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	int n;

	cin >> n;

	vector<int> numV(n);
	vector<bool> checkV(n, false);

	for (int i = 0; i < n; i++)
		cin >> numV[i];

	for (int i = 1; i < n; i++)
	{
		int pos = numV[i] - numV[i - 1];
		pos = pos > 0 ? pos : -pos;

		if (pos > 0 && pos < n && checkV[pos] == false)
			checkV[pos] = true;
		else
		{
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";
	return 0;
}