모바일 TCG 마비노기 듀얼에는 다섯 종류의 자원이 있다. 자원은 각각 골드, 마나, 빛, 어둠, 자연이라 불린다.
카드들은 자원에 따라 구분된다. 예를 들어, 다음 카드를 보면 맨 위에 파란색 병 모양의 아이콘이 있는데, 이는 이 카드를 사용하려면 마나를 요구함을 뜻한다.
게임을 진행하려면 이 카드들을 12장 이하로 모아 하나의 덱(deck)을 구성해야 한다. 이때, 각 덱은 최대 세 종류의 자원을 섞어서 구성할 수 있다.
12장 이하의 카드들이 요구하는 자원의 목록이 주어질 때, 이 카드들이 올바른 덱을 구성하는지 아닌지 판단하는 프로그램을 작성하여라.
입력
첫 줄에 카드의 수 �N이 주어진다. �N은 1 이상 12 이하이다. 다음 �N개의 줄에 걸쳐
gold(골드), mana(마나), light(빛), dark(어둠), nature(자연) 중 하나의 문자열이 주어진다. 이는 각 카드가 요구하는 자원을 뜻한다.출력
주어진 카드들이 올바른 덱을 구성한다면
valid를, 아니라면 invalid를 출력한다.예제 1
입력
12 gold gold gold gold gold gold gold gold gold gold gold gold
출력
valid
단일 자원으로 구성된 덱은 올바른 덱이다.
예제 2
입력
12 light light light light nature mana mana nature mana mana mana nature
출력
valid
세 종류의 자원으로 구성된 덱은 올바른 덱이다.
예제 3
입력
5 gold mana light dark nature
출력
invalid
다섯 종류의 자원으로는 덱을 구성할 수 없다.
예제 3
입력
12 light light light dark dark light light light light light dark light
출력
valid
풀이
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include <list> #include<map> using namespace std; #define MAX 13 int N; string Dec[MAX]; map<string, int> card; void Input() { cin >> N; for (int i = 0; i < N; i++) { cin >> Dec[i]; card[Dec[i]]++; } } void Solution() { if (card.size() >= 4) cout << "invaild"; else cout << "vaild"; } void Solve() { Input(); Solution(); } int main() { Solve(); }
map을 하나 선언해준다. 카드가 새로 등록될 때 마다. map의 배열이 동적으로 생성 될 것이다.
card size가 4보다 크거나 같으면 invaild를 출력하고, 작다면 vaild를 호출해준다.
map을 사용한 이유는 완탐을 통해 검사 하는 방법도 고려할 수 있었지만 탐색에 따른 오버헤드와
코드의 길이가 많이 길어지므로 깔끔하게 풀이하고 싶었다.