[Baekjoon/C++] 33575번 - 시간표

[백준] Baekjoon Online Judge

문제로 이동

 

문제

디미고에 입학한 동현이는 고등학교 인생 첫 시간표를 받게 되었다. 누구나 그렇듯이 동현이도 좋아하는 과목과 싫어하는 과목이 있다. 동현이는 시간표에 자신이 좋아하는 과목이 많을수록 기분이 좋아진다. 학생마다 수업 시간표에 과목들이 어떻게 배치되어 있느냐에 따라 선호도가 달라지는데, 동현이의 시간표 선호도는 다음과 같은 방법으로 계산할 수 있다.

• 동현이의 시간표 선호도 기본값은 0이다.
• 동현이가 좋아하는 과목이 3교시 이상 연속으로 등장할 경우 선호도가 연속으로 등장한 과목의 개수만큼 증가한다.
• 동현이가 싫어하는 과목이 3교시 이상 연속으로 등장할 경우 선호도가 연속으로 등장한 과목의 개수만큼 감소한다.

동현이가 좋아하는 과목과 싫어하는 과목이 주어질 때 동현이의 시간표 선호도를 출력하는 프로그램을 작성하시오. 각 과목은 1부터 M사이의 정수로 표현된다.

 

입력

첫 번째 줄에 시간표의 길이 N, 과목의 개수 M, 동현이가 좋아하는 과목의 개수 A, 동현이가 싫어하는 과목의 개수 B가 공백으로 구분하여 주어진다. (3 ≤ N, M ≤ 105; 1 ≤ A, B < M; A + B ≤ M)

두 번째 줄에 시간표 T1,T2,⋯,TN이 순서대로 공백으로 구분하여 주어진다. (1 ≤ T1, T2, ⋯, TN ≤ M)

세 번째 줄에 동현이가 좋아하는 서로 다른 A개의 과목 L1,L2,⋯,LA이 공백으로 구분하여 주어진다. (1 ≤ L1, L2, ⋯, LA ≤ M)

네 번째 줄에 동현이가 싫어하는 서로 다른 B개의 과목 H1,H2,⋯,HB가 공백으로 구분하여 주어진다. (1 ≤ H1, H2, ⋯, HB ≤ M)

동현이가 좋아하면서 동시에 싫어하는 과목은 없으며, 좋아하지도 싫어하지도 않는 과목이 존재할 수 있다.

 

출력

첫 번째 줄에 동현이의 시간표 선호도를 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

#define MAX 100001

int N, M, A, B;
int arr[MAX];
int like[MAX];

int preference();

int preference() {
	int num = 0;	// 연속으로 등장 중인 선호도
	int cnt = 0;	// 연속으로 등장한 횟수
	int result = 0;	// 시간표 선호도

	for (int i = 0; i < N; i++) {
		// 연속 등장이 끝나면
		if (like[arr[i]] != num) {
			// 연속으로 3교시 이상 등장한 경우
			if (cnt >= 3) result += (cnt * num);

			num = 0;
			cnt = 0;
		}

		num = like[arr[i]];
		cnt++;
	}

	// 연속으로 3교시 이상 등장한 경우
	if (cnt >= 3) result += (cnt * num);

	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M >> A >> B;
	for (int i = 0; i < N; i++) cin >> arr[i];

	while (A--) {
		int n;
		cin >> n;

		like[n] = 1;
	}

	while (B--) {
		int n;
		cin >> n;

		like[n] = -1;
	}

	cout << preference() << '\n';

	return 0;
}

 

int preference() {
	int num = 0;	// 연속으로 등장 중인 선호도
	int cnt = 0;	// 연속으로 등장한 횟수
	int result = 0;	// 시간표 선호도

	for (int i = 0; i < N; i++) {
		// 연속 등장이 끝나면
		if (like[arr[i]] != num) {
			// 연속으로 3교시 이상 등장한 경우
			if (cnt >= 3) result += (cnt * num);

			num = 0;
			cnt = 0;
		}

		num = like[arr[i]];
		cnt++;
	}

	// 연속으로 3교시 이상 등장한 경우
	if (cnt >= 3) result += (cnt * num);

	return result;
}

 좋아하는 과목이든 싫어하는 과목이든 연속으로 3교시 이상 등장했을 때만 선호도에 변화를 줘야 한다.