[C++]Softeer/HSAT Level2- 비밀 메뉴

<문제>

https://softeer.ai/practice/info.do?idx=1&eid=623 

Softeer

회사 식당에는 전설처럼 전해 내려오는 비밀 메뉴에 대한 소문이 있다. 소문의 내용은 대강 이러하다.
식권 자판기의 버튼을 특정 순서대로 누르고 결제를 하면, 평소와는 다른 색깔의 식권이 나온다.

이 식권을 배식대에 제출하면, 어떤 비밀 메뉴를 받을 수 있다는 것이다. 물론 이를 실제로 본 사람은 아무도 없어서, 어떤 메뉴가 나오는지는 커녕 눌러야 하는 버튼의 순서조차 알려져 있지 않다.

주방장인 당신은 이 소문의 실체를 알고 있다. 이는 분명한 사실이다!
정해진 버튼 조작법을 사용하면 비밀 메뉴의 식권을 얻을 수 있다. 그러나 얼마 전 식권 자판기가 고장으로 교체되면서, 새 자판기에서는 비밀 메뉴 조작법이 작동하지 않게 되었다.

당신은 프로그래밍 실력을 살려, 사용자의 버튼 조작 중 비밀 메뉴 조작법이 포함되어 있는지를 판단하는 회로를 추가하려 한다.

자판기에는 총 K개의 버튼이 있다. 각 버튼마다 1부터 K까지 번호가 붙어 있어서, 조작 과정은 1 이상 K 이하의 정수 여러 개로 나타낼 수 있다.
비밀 메뉴 조작법은 M개의 버튼 조작으로 이루어져 있으며, 이 순서대로 버튼을 누르면 반드시 비밀 메뉴 식권이 발매된다. 이때, 이 조작법 앞뒤로 다른 버튼 조작이 있어도 비밀 메뉴로 인정된다.

사용자가 누른 N개의 버튼 조작이 주어질 때, 사용자가 비밀 메뉴 식권을 받을 수 있는지를 확인하는 프로그램을 작성하여라.

제약조건
1 ≤ K ≤ 9
1 ≤ M ≤ 100
1 ≤ N ≤ 100
각 버튼의 번호는 1 이상 K 이하이다.

 

<제출답안>

#include<iostream>

using namespace std;

int K, M, N;
int add_term = 1;

int Answer[110];
int User_Input[110];

#define SECRET 1
#define NORMAL 0

int dfs(int k)
{
	if(add_term == M)
		return SECRET;

	if(User_Input[k+add_term] == Answer[add_term])
	{
		add_term ++ ;
		dfs(k);
	}
	else
	{
		return NORMAL;
	}
}

int main(int argc, char** argv)
{
	cin>>M;		// Answer
	cin>>N;		// User Input
	cin>>K;		// 1~5

	for(int i=0;i<M;i++)
		cin>>Answer[i];
	
	for(int j=0;j<N;j++)
		cin>>User_Input[j];
	
	int output = NORMAL ;
	int k=0;
	for(k=0;k<N;k++)
	{
		if(User_Input[k] == Answer[0])
		{
			add_term = 1;
			output = dfs(k);
			if(output == SECRET)
			{
				cout<<"secret"<<endl;
				return 0;
			}
		}
	}

	cout<<"normal"<<endl;
	return 0;
}

 

연속으로 비밀숫자를 맞추면 되는 문제이므로, 비밀숫자의 첫번째가 동일한 시점에서 DFS를 돌리면 된다.

비밀숫자의 끝까지 비교하면되는데,

중간에 다른 숫자가 나오면 Normal로/ 모두 같은 숫자이면 Secret으로 return한다.

Secret일 경우 바로 secret을 출력하고 return0으로 main문을 빠져나온다.