moner_ari   1년 전

[문제]

소들은 평소와 같이 어설프게 주사위를 굴리는 게임인 Yahtzee를 즐기고 있습니다. 소들은 S개(1 <= S <= 8)의 면이 있는 N개(1 <= N <= 20)의 주사위를 굴립니다. 그들은 ("3개의 2를 포함하는" 또는 "1개의 2와 2개의 3을 포함하는"과 같은) 특정 조건에 맞는, 주사위를 굴리는 경우의 수를 알고 싶어합니다.

소들이 경우의 수를 배울 수 있도록 도와주세요. N, S와 소들이 제시한 기준을 나타낸 여러 수식을 입력받은 후, 아래 조건에 맞는 프로그램을 작성하세요. 주사위를 굴릴 수 있는 모든 경우의 수에 대해, 입력받은 수식을 충족시키는 경우의 수를 세야 합니다. (참고로, 면이 2개인 주사위 3개를 굴리는 모든 경우의 수는 {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2}입니다.)

각 수식은 "적어도 W개 이상의 R가 나와야 한다"는 것을 표현하는 기본 양식의 조합으로 구성됩니다. 이때 기본 양식은 0 <= W <= N, 1 <= R <= S를 충족하는 다음의 수식으로 표현할 수 있습니다.

WxR

각 테스트 케이스마다 E개(1 <= E <= 20)의 수식이 입력되는데, 각 수식은 1개 이상 10개 이하의 위 기본 양식이 0~9개의 '+'로 연결된 형식으로 주어집니다. (이때 '+'는 AND를 의미합니다.) 또한, 각 E개의 수식은 서로 'inclusive OR' 조건으로 묶여 있습니다. 그러므로, 아래 표현은 "3개 이상의 5를 포함하거나, 1개 이상의 3과 2개 이상의 4를 포함할 것"을 의미합니다.

3x5
1x3+2x4

5개의 면을 가진 주사위 4개를 굴릴 때, 위 표현을 만족시키는 주사위 눈의 조합은 {5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3; 3,4,4,5; 4,4,5,3.}입니다.

주의: 1번째 줄에서는 2개 이상의 자연수를 입력받은 후, 2번째 줄부터는 문자열을 입력받아야 합니다. 몇몇 언어들의 경우 입출력 양식이 생각보다 까다로울 수 있습니다! 또한, 채점 데이터에는 주사위를 굴리는 모든 경우의 수가 절대 1,512,768개를 초과하지 않습니다.

--------

[입력]

  • 1번째 줄: 3개의 정수 N, S, E가 공백으로 구분되어 주어집니다.
  • 2번째 줄 이후, E개의 줄: 문제 지문에서 설명한 것과 같이 E개의 수식이 한 줄에 하나씩 문자열로 주어집니다.

--------

[출력]

  • 1번째 줄: S개의 면을 가진 N개의 주사위를 굴리는 모든 경우 중에서, E개의 수식을 만족시키는 경우의 수를 하나의 정수로 출력합니다.

댓글을 작성하려면 로그인해야 합니다.