[백준 25194] 결전의 금요일 (C++)

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

25194번: 결전의 금요일

문제

---

 

곰곰이는 올해도 운동하기를 신년 목표로 삼았지만, 지금까지 헬스장을 한 번도 가지 않았다. 운동하라고 잔소리하는 당신에게, 곰곰이는 금요일에 정확히 일을 끝마치는 시점이 있다면 헬스장을 가겠다고 한다!

곰곰이에게는 N개의 일이 주어졌고, i번째 일을 끝마치는데는 A_i일이 걸린다.

월요일인 지금, 당신은 곰곰이에게 주어진 일의 순서를 적절히 바꿔서 곰곰이를 헬스장에 보낼 방법이 있는지 알고 싶다.

 

입력

---

첫 번째 줄에는 일의 개수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 1,000)

두 번째 줄에는 정수 A₁, A₂, ⋯ , A_N이 공백을 사이에 두고 주어진다. (1 ≤ A₁,A₂,⋯,A_N ≤ 100,000)

 

출력

---

곰곰이를 헬스장에 보낼 수 있다면 YES를, 불가능하다면 NO를 첫째 줄에 출력한다.

 

문제 풀이

---

dp 문제.

특정 요일에 일을 끝낼 수 있는지를 dp 배열로 선언한다. 0은 일요일, 1은 월요일, ...6은 토요일로 둔다. 오늘인 월요일을 true로 초기화 한 후 월요일에 A₁일을 더한 후 7로 나누면 첫번째 일을 끝냈을 때의 요일을 알 수 있다. 해당 요일을 true로 바꾼다. 마찬가지로 i번째 일 이전에 일을 끝낼 수 있는 모든 요일에 A_i일을 더하면 i번째 일을 했을 때 마치는 요일을 모두 구할 수 있다. 금요일인 dp[5]가 true로 바뀐다면 금요일에 일을 끝낼 수 있고, false라면 금요일에 일을 끝낼 수 없다.

 

다음과 같은 예시를 들어보자.

3
1 5 6

초기 상태는 다음과 같다.

 

0 (일)	1 (월)	2 (화)	3 (수)	4 (목)	5 (금)	6 (토)
false	true	false	false	false	false	false

---

첫번째 일을 끝내면 1일이 지나 화요일이 된다. dp[2]을 true로 바꾼다.

0 (일)	1 (월)	2 (화)	3 (수)	4 (목)	5 (금)	6 (토)
false	true	true	false	false	false	false

---

두번째 일은 첫번째 일을 끝내고 할 수도 있고(화요일에서 시작해서 일요일에 끝난다.), 첫번째 일을 하지 않고 할 수 있다. (월요일에 시작해서 토요일에 끝난다.) 즉, 일을 끝낸 요일 + 두번째 일에 소요되는 일 수가 두 번째 일을 끝냈을 때의 요일이다. 일요일과 토요일을 true로 바꾼다.

0 (일)	1 (월)	2 (화)	3 (수)	4 (목)	5 (금)	6 (토)
true	true	true	false	false	false	true

---

세번째 일은 앞서 true인 요일+ 세번째 일에 소요되는 일 수를 통해 세번째 일까지의 요일을 알 수 있다. 세번째 일까지 가능한 요일은 토요일, 일요일, 월요일, 금요일이다.

 

0 (일)	1 (월)	2 (화)	3 (수)	4 (목)	5 (금)	6 (토)
true	true	true	false	false	true	true

*토요일: 첫번째 o-두번째 o-세번째 o

일요일: 첫번째 x-두번째 x-세번째 o

월요일: 첫번째 x- 두번째 x-세번째 x

금요일: 첫번째 x-두번째 o-세번째 o

 

아래는 코드.

#include <iostream>
#include <vector>
using namespace std;

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

	int N;
	long long sum = 0;
	cin >> N;
	int* arr = new int[N];
	bool* dp = new bool[7];
	bool canGo = false;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < 7; i++)
	{
		dp[i] = false;
	}
	dp[1] = true;
	for (int i = 0; i < N; i++)
	{
		vector<int> tempV;
		for (int j = 0; j < 7; j++)
		{
			if (dp[j] == true)
			{
				tempV.push_back(j);
			}
		}
		for (int j = 0; j < tempV.size(); j++)
		{
			dp[(tempV.at(j) + arr[i]) % 7] = true;
		}
		if (dp[5] == true)
		{
			canGo = true;
			break;
		}
	}
	if (canGo == true)
	{
		cout << "YES" << "\n";
	}
	else
	{
		cout << "NO" << "\n";
	}
	return 0;
}