2907번 - 재료 사러 가는 길 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 33 | 13 | 11 | 42.308% |
문제
세상에서 제일 바쁜 동혁이는 팬케익을 좋아한다. 오늘은 집에서 팬케익을 만들어 먹기로 결심했다. 주방을 뒤져 열심히 팬케익을 만들 재료 4가지 밀가루, 우유, 계란, 잼을 찾았지만, 집에는 재료가 하나도 없었다. 그는 주변의 상점을 돌아다니면서 재료를 사오려고 한다.
동혁이네 동네에는 교차로가 N개 있고, 1번부터 N번까지 번호가 매겨져 있다. 그리고 도로는 총 R개가 있고, 교차로와 교차로를 잇는다.
동혁이는 지금 1번 교차로에 있다. 각 도로에는 상점이 항상 1개가 있고, 상점에서는 4개 재료 중 일부만 팔 수도 있고, 모두 팔 수도 있다. 상점을 방문하지 않고 도로를 지나는데 걸리는 시간은 1분이고, 상점을 방문해 재료를 구매하고 지나면 2분이 걸린다.
동혁이는 모든 재료를 구한 뒤, 1번 교차로로 다시 돌아오려고 한다. 그는 재료를 모두 구했다고 하더라도 상점간의 가격 비교를 위해서 상점을 방문할 수 있다.
아래와 같이 교차로 5개, 도로 7개인 경우를 살펴보자. (밀가루: B, 계란: J, 우유: M, 잼: P)
위와 같은 경우라면, 7분안에 모든 재료를 구하는 서로 다른 방법은 아래와 같이 5가지가 있다.
| 1분 | 2분 | 3분 | 4분 | 5분 | 6분 | 7분 |
| 1→3 | 3->상점->4 | 4→상점→1 | ||||
| 1→상점→2 | 2→상점→4 | 4→상점→1 | ||||
| 1→상점→3 | 3→상점→4 | 4→상점→1 | ||||
| 1→상점→3 | 3→상점→4 | 4→5 | 4→상점→1 | |||
| 1→3 | 3→상점→4 | 4→상점→5 | 5→상점→1 | |||
동혁이가 1번 교차로에서 출발서 모든 재료를 구한 뒤 다시 1번 교차로로 K분안에 돌아오는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.
이 숫자는 매우 커질 수 있으므로 5557로 나눈 나머지를 출력한다.
입력
첫째 줄에 N과 R이 주어진다. (1<=N<=25, 1<=R<=500)
둘째 줄부터 R개의 줄에는 도로의 정보가 주어진다. 도로의 정보는 서로 다른 정수 u, v와 문자열 s가 공백으로 구분되어 있다. u와 v를 잇는 도로가 있고, 여기에 있는 상점에서 파는 재료는 s라는 의미이며, s는 1글자~4글자 알파벳 대문자이며, 밀가루는 B, 달걀은 J, 우유는 M, 잼은 P이다. 두 교차로 사이에는 도로가 최대 2개까지 있을 수 있으며, 2개인 경우에는 방향이 서로 달라야 한다. (u->v와 v->u)
마지막 줄에는 동혁이가 모든 재료를 구하고 다시 돌아 와야 하는 시간 제한 K(1<=K<=1,000,000,000)가 주어진다.
출력
첫째 줄에 동혁이가 K분 안에 모든 재료를 구하고 다시 1번 교차로로 돌아오는 서로 다른 방법의 수를 5557로 나눈 나머지를 출력한다.
예제 입력 1
3 3 1 2 BMJ 2 3 MJP 3 1 JPB 5
예제 출력 1
3
예제 입력 2
3 4 1 2 B 2 1 P 1 3 J 3 1 M 8
예제 출력 2
2
예제 입력 3
5 7 1 2 B 2 4 M 1 3 J 3 4 MB 4 1 JP 4 5 J 5 1 P 7
예제 출력 3
5
출처
Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #4 6번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호