[백준 BOJ] 4383번 점프는 즐거워 (C++/cpp)

문제 설명

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

4383번: 점프는 즐거워

 

접근 방법 - 배열을 이용한 연산이 필요한 수학 문제

백준의 4383번 문제는 배열을 이용하여 해결해야 하는 수학적 연산 문제이다.

해당 문제는, 입력받은 수열에 있어 각 구간의 차가 1에서 n-1까지 모두 존재하는지를 파악해야 하는 문제이다. (n : 수열의 길이)

(구체적인 설명은 반드시 문제를 참고하길 바란다.)

필자는 문제에서 설명하는 구간의 차가 모두 존재하는지를 배열을 통해 카운팅해보았다.

여기서 필자는, 시간 초과를 방지하기 위해 수열을 하나씩 입력받으면서 구간의 차를 연산하였고 그 즉시 카운팅을 실행하도록 하였다.

자세한 설명은 아래에 작성해보았으니, 해결에 어려움을 겪고 있다면 아래의 코드와 설명을 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 무한 반복문을 실행하여 테스트 케이스의 입력값들을 하나씩 받는다.

- 수열의 길이(n)를 입력받는다. 여기서 n이 입력되지 않을 시, 해당 반복문을 종료한다.

- n의 크기가 1이라면, 이는 반드시 Jolly Jumper로 판별된다. 따라서 "Jolly"를 출력하고 다음 테스트 케이스를 실행한다.

- n의 크기가 2 이상이라면 다음 입력을 받도록 한다.

 

2) 수열값들을 저장할 배열(arr)을 선언한다.

그리고 구간의 차를 카운팅할 배열(cnt)을, 배열값을 모두 0으로 초기화하여 선언한다.

 

3) n의 크기만큼 수열값들을 하나씩 입력받고, 다음의 연산을 수행한다. (여기서 연산은 두 번째 수열값부터 진행한다.)

- 임의의 변수 num에 구간의 차를 저장한다.

- num이 양수일 경우, 이 값을 배열 번호로 갖는 cnt의 배열값에 1을 더한다.

- num이 음수일 경우, 이 값을 양수로 변경하고 이것을 배열 번호로 갖는 cnt의 배열값에 1을 더한다.

 

4) 수열값의 입력과 연산이 모두 끝났다면, 반복문으로 cnt의 값들을 탐색하여 해당 수열이 Jolly Jumper인지를 판별한다.

- 현재 탐색하는 배열값이 0이라면, 해당 값을 어느 구간의 차로도 가지지 않는다는 것을 뜻한다. 따라서 이때엔 "Not jolly"를 출력하고 다음 테스트 케이스를 수행한다.

- n-1까지 해당 반복문을 수행하고 있다면, 모든 구간의 차를 가지고 있다는 것을 뜻한다. 따라서 이때엔 "Jolly"를 출력한다.

 

5) 모든 테스트 케이스가 종료되었을 시, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 4383번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	while (1) {
		int n;
		cin >> n;

		int arr[3000];	//입력값
		if (cin.eof() == 1) { break; }
		else if (n == 1) { 
			int a;
			cin >> a;
			cout << "Jolly" << endl;
		}
		else {
			int cnt[3000] = { 0 };
			for (int i = 0; i < n; i++) {
				cin >> arr[i];
				if (i == 0) { continue; }
				int num = arr[i] - arr[i - 1];
				if (num > 0) { cnt[num]++; }
				else { cnt[num * (-1)]++; }
			}
			for (int i = 1; i < n; i++) {
				if (cnt[i] == 0) { cout << "Not jolly" << endl; break; }
				if (i == n - 1) { cout << "Jolly" << endl; }
			}
		}
	}
}

 

제출 결과

(2022.04.18 백준 4383번 문제 제출 결과)

실버5 치고는 꽤 복잡한 로직을 가지고 있었던 것 같다...