10759번 - 팰린드롬 경로 3 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 454 | 179 | 129 | 39.571% |
문제
N * N 크기의 격자모양의 농장이 있다. (1≤N≤500). 격자의 간 칸들에는 알파벳이 한글자씩 쓰여 있다. 예를 들어 아래와 같은 식이다 (N=4)
ABCD BXZX CDXB WCBA
농장에 사는 귀여운 송아지가 한마리 있는데, 이 송아지가 지금 농장의 왼쪽 위 (1,1)에서 출발하여 엄마소가 있는 곳(N,N)으로 가려고 한다. 송아지는 엄마가 너무 보고 싶기 때문에 오른쪽 또는 아래로만 움직인다. 송아지는 아직 어려서 길을 잘 모른다. 그래서 바닥에 쓰여진 알파벳을 보고 길을 찾아간다. 하지만 만약에 송아지가 출발점에서 도착점까지 가면서 만들게 되는 경로가 팰린드롬이라면 앞뒤를 구분하지 못해서 길을 잃어버린다.
귀여운 송아지가 길을 잃지않고 엄마소를 찾을 수 있도록 1,1 에서 출발하여 N,N까지 가는 경로 중 팰린드롬인 경로의 개수를 계산하여 알려주자.
답이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
입력
첫 번째 줄에 격자의 크기 N이 주어지고, 두번째 줄 ~ N+1번째 줄에 걸쳐 농장에 쓰여진 알파벳이 주어진다. 알파벳은 대문자로만 이루어져 있다.
출력
1,1에서 N,N으로 가는 경로 중 팰린드롬인 경로의 개수를 1,000,000,007로 나눈 나머지를 출력하라.
예제 입력 1
4 ABCD BXZX CDXB WCBA
예제 출력 1
12
힌트
위 예제에서 만들 수 있는 팰린드롬은 아래와 같다.
- 1 x "ABCDCBA"
- 1 x "ABCWCBA"
- 6 x "ABXZXBA"
- 4 x "ABXDXBA"
1 + 1 + 6 + 4 = 12
출처
Olympiad > USA Computing Olympiad > 2014-2015 Season > USACO US Open 2015 Contest > Gold 2번
- 문제를 번역한 사람: algoshipda
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호