[백준 28706] 럭키 세븐 (C++)

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

문제

---

당신은 양의 정수 K를 하나 가지고 있습니다. 처음에 K=1입니다.

당신에게는 N개의 턴이 주어지고, 각 턴에는 2개의 선택지 중 하나를 골라야합니다. 각각의 선택지는 “+ v” 혹은 “* v”와 같은 방식으로 주어집니다. (1 ≤ v ≤ 9)

• “+ v ”: K를 K+v로 바꿉니다.
• “* v ”: K를 K×v로 바꿉니다.

선택지를 모두 고른 이후 결과로 나온 K가 7의 배수가 되도록 할 수 있나요?

입력

---

첫 줄에 테스트케이스의 수 T가 주어집니다. (1 ≤ T ≤ 10000)

각 테스트케이스의 첫 줄에 턴의 수 N이 주어집니다. (1 ≤ N ≤ 200000)

다음 N개의 줄의 i번째 줄은 “ op1 v1 op2 v2 ”와 같은 방식으로 모든 문자를 공백으로 구분하여 주어집니다. op1과 op2는 ‘+’ 혹은 ‘*’이며, v1과 v2는 1이상 9 이하의 정수입니다. 이는 i번째 턴의 선택지가 “ op1 v1 ”과 “ op2 v2 ”라는 것을 의미합니다.

모든 테스트케이스에서 N의 합이 200000을 넘지 않습니다.

 

출력

---

각 테스트케이스마다 한 줄에 하나씩, K를 7의 배수로 만들 수 있다면 “LUCKY”, 불가능하다면 “UNLUCKY”를 출력하세요.

 

문제 풀이

---

dp 문제.

 

어떤 수 A와 B가 i로 나누었을 때 나머지가 같다면 A와 B에 같은 수를 곱하거나 더해도 나머지가 같다. 이를 이용하여 (N+1) * 7짜리 크기의 배열을 만들어 i-1번째에서 만든 수(나머지만 저장되어 있음)로부터 특정 수를 곱하거나 더했을 때 i번째 줄에 나머지가 몇인지 계산해주면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int calcRemain(char op, int num, int j)
{
	if (op == '*')
	{
		return (num * j) % 7;
	}
	else
	{
		return (num + j) % 7;
	}
}

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

	int N, T;
	char op1, op2;
	int num1, num2;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		cin >> N;
		bool** dp = new bool* [N + 1];
		for (int i = 0; i < N + 1; i++)
		{
			dp[i] = new bool[7];
			for (int j = 0; j < 7; j++)
			{
				dp[i][j] = false;
			}
		}
		dp[0][1] = true;
		for (int i = 1; i <= N; i++)
		{
			cin >> op1 >> num1 >> op2 >> num2;
			for (int j = 0; j < 7; j++)
			{
				if (dp[i - 1][j] == true)
				{
					dp[i][calcRemain(op1, num1, j)] = true;
					dp[i][calcRemain(op2, num2, j)] = true;
				}
			}
		}
		if (dp[N][0] == false)
		{
			cout << "UNLUCKY" << "\n";
		}
		else
		{
			cout << "LUCKY" << "\n";
		}
	}
	return 0;
}