4257번 - 프리오더 포스트오더 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 20 | 17 | 15 | 83.333% |
문제
이진 트리를 인오더(in-order)와 포스트오더(post-order)로 순회한 결과가 주어졌을 때, 프리오더(pre-order)로 순회한 결과를 찾을 수 있다. 또, 인오더와 포리오더로 순회한 결과가 주어졌을 때, 포스트오더로 순회한 결과도 쉽게 찾을 수 있다. 하지만, 프리오더와 포스트오더로 순회한 결과가 주어졌을 때는, 인오더로 순회한 결과를 구할 수 없다.
아래 이진 트리 4개를 보자.
위의 트리는 같은 프리오더와 포스트오더를 갖는 트리이다. 이러한 현상은 이진 트리에서만 나타나는 것이 아니고, 모든 m진 트리(자식이 최대 m개인 트리)에서 나타난다.
m진 트리를 프리오더와 포스트오더로 순회한 결과가 주어졌을 때, 이러한 순회 결과를 갖는 트리의 개수를 출력하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같은 형식이다.
m s1 s2
이 뜻은 m진트리를 프리오더 순회한 결과가 s1, 포스트오더로 순회한 결과가 s2라는 뜻이다. (1 ≤ m ≤ 20, 1 ≤ s1,s2의 길이 ≤ 26, s1의 길이 = s2의 길이) s1의 길이가 k일 때, 알파벳 첫 k개 문자가 사용된다. 마지막 줄은 0이 주어진다.
출력
각 테스트 케이스에 대해서, 입력으로 주어진 프리오더와 포스트오더 순회 결과를 갖는 m진트리의 개수를 출력한다. 이 결과는 항상 부호있는 32비트 정수 범위이다. 입력으로 주어진 결과를 이용해서 트리를 적어도 하나는 만들 수 있다.
예제 입력 1
2 abc cba 2 abc bca 10 abc bca 13 abejkcfghid jkebfghicda 0
예제 출력 1
4 1 45 207352860
출처
ICPC > Regionals > North America > East Central North America Regional > 2002 East Central Regional Contest D번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호