1497번

수정 전

시간 제한 메모리 제한
2 초 128 MB

문제

  세준이는 기타리스트이고, 공연을 하려고 한다. 하지만, 세준이는 기타를 모두 도둑맞았기 때문에, 기타가 하나도 없다. 그래서, 기타를 좀 사려고 한다.

  세준이는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 그 이유는 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 세준이는 이런 일을 용납하지 않는다.

  모든 곡을 제대로 연주하기 위해 필요한 기타의 개수를 최소화하는 프로그램을 작성하시오.

  예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 연주할 수 있고, ESP로 1번곡을 제대로 연주할 수 있다면, 세준이는 EPIPHONE과 GIBSON을 사면 최소의 개수로 모든 곡을 연주할 수 있다. 
 

입력

  첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 정보가 차례대로 주어진다. Y는 연주할 수 있는 것이고, N은 없는 것이다.
 

출력

  첫째 줄에 필요한 기타의 개수를 출력한다. 만약 모든 곡을 연주할 수 없으면 -1을 출력한다.
 

예제 입력

4 5 GIBSON YYYNN FENDER YYNNY EPIPHONE NNNYY ESP YNNNN

예제 출력

2

힌트

수정 후

시간 제한 메모리 제한
2 초 128 MB

문제

  세준이는 기타리스트이고, 공연을 하려고 한다. 하지만, 세준이는 기타를 모두 도둑맞았기 때문에, 기타가 하나도 없다. 그래서, 기타를 좀 사려고 한다.

  세준이는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 그 이유는 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 세준이는 이런 일을 용납하지 않는다.

  최대한 많은 곡을 제대로 연주할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오.

  예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 연주할 수 있고, ESP로 1번곡을 제대로 연주할 수 있다면, 세준이는 EPIPHONE과 GIBSON을 사면 최소의 개수로 모든 곡을 연주할 수 있다. 
 

입력

  첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 정보가 차례대로 주어진다. Y는 연주할 수 있는 것이고, N은 없는 것이다.
 

출력

  첫째 줄에 필요한 기타의 개수를 출력한다. 만약 연주할 수 있는 곡이 없으면 -1을 출력한다.
 

예제 입력

4 5 GIBSON YYYNN FENDER YYNNY EPIPHONE NNNYY ESP YNNNN

예제 출력

2

힌트