[ HackerRank] Attending Workshops

https://www.hackerrank.com/challenges/attending-workshops/problem

Attending Workshops | HackerRank

문제 풀이)

 

워크 샵의 종류와 워크 샵의 시작 시간, 진행 시간이 주어질 때, 학생들이 시간이 겹치지 않게 워크 샵을 최대한

 

몇 번 참여할 수 있는 지 출력해주는 문제이다.

 

시작 시간 혹은 끝 시간 둘 중 하나를 기준으로 잡고 DP 배열을 이용하여 풀면 된다.

 

먼저 워크 샵의 시작 시간의 최대치, 즉 가장 늦게 시작하는 경우는 1000초 이므로 dp배열의 크기는 최소

 

1001개 이상이어야 한다.

 

또한 워크 샵의 시간이 겹치지 않아야 하므로 시작 시간이 같은 워크샵이 여러개일 경우엔 단 하나만 들을 수 있다.

 

따라서 진행 시간이 가장 짧은 워크샵을 제외한 나머지는 모두 지워주었다.

 

이제 1000초부터 0초까지 돌면서,

 

dp[i] = max((1 + dp[워크샵 끝나는 시간]), dp[i + 1]); 의 형태가 된다.

 

1 + dp[워크샵 끝나는 시간] 은 현재 워크 샵을 들었을 경우이고 dp[i + 1]은 현재 워크샵을 듣지 않은 경우이다.

 

이와 같이 dp 배열을 역으로 채워주고, 마지막 dp[0]을 리턴해주면 된다. 

 

시작 시간을 기준으로 했는데, 만약 끝나는 시간을 기준으로 하고 싶다면 dp배열은 앞에서부터 채워질 것이다. 

 

#include<bits/stdc++.h>

using namespace std;

//Define the structs Workshops and Available_Workshops.
//Implement the functions initialize and CalculateMaxWorkshops
struct Workshops
{
	Workshops(int s = 0, int d = 0, int e = 0) :
		start_time(s), duration(d), end_time(e)
	{
	}
	int start_time;
	int end_time;
	int duration;

	void setTimes(int s, int d, int e)
	{
		start_time = s;
		duration = d;
		end_time = e;
	}
};

struct Available_Workshops
{
	Available_Workshops() :
		pWs(NULL), nSize(0)
	{
	}
	~Available_Workshops()
	{
		if (pWs)
			delete[] pWs;
		nSize = 0;
	}

	Workshops *pWs;
	int nSize;
};
typedef Available_Workshops AW;
typedef Workshops WS;

AW* initialize(int* st, int* dr, int size)
{
	AW* pAws = new AW;
	pAws->pWs = new WS[size];
	pAws->nSize = size;

	for (int i = 0; i < size; ++i)
		pAws->pWs[i].setTimes(st[i], dr[i], st[i] + dr[i]);

	return pAws;
}

const int CalculateMaxWorkshops(AW *pAws) {
	int *dp = new int[1010];
	WS **pStartWs = new WS *[1010];
	for (int i = 0; i < 1010; ++i) {
		pStartWs[i] = 0;
		dp[i] = 0;
	}

	for (int i = 0; i < pAws->nSize; ++i) {
		int start_time = pAws->pWs[i].start_time;
		if (!pStartWs[start_time])
			pStartWs[start_time] = &pAws->pWs[i];
		else if (pStartWs[start_time]->duration > pAws->pWs[i].duration)
			pStartWs[start_time] = &pAws->pWs[i];
	}

	for (int i = 1000; i >= 0; --i) {
		if (!pStartWs[i]) {
			dp[i] = dp[i + 1];
			continue;
		}
		if (pStartWs[i]->end_time <= 1000)
			dp[i] = (1 + dp[pStartWs[i]->end_time] > dp[i + 1]
				? 1 + dp[pStartWs[i]->end_time]
				: dp[i + 1]);
		else
			dp[i] = 1 > dp[i + 1] ? 1 : dp[i + 1];
	}
	return dp[0];
}

int main(int argc, char *argv[]) {
	int n; // number of workshops
	cin >> n;
	// create arrays of unknown size n
	int* start_time = new int[n];
	int* duration = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> start_time[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> duration[i];
	}

	Available_Workshops * ptr;
	ptr = initialize(start_time, duration, n);
	cout << CalculateMaxWorkshops(ptr) << endl;
	return 0;
}