https://www.acmicpc.net/problem/3706
문제요약
- 알파벳 26개의 permutation으로 "ABCD.....Z"를 변환함(1:1 변환)
- 어떤 문자열 S가 주어질때 "ABC....Z"를 두번 변환해서 가능한 문자열인지 판단
- 500개 테스트케이스
접근법
- 처음에는 뭔가? 함
- 한번 변환은 항상 되겠지
- 두번 변환으로 안되는 경우가 있나?
- permutation 개수 만큼 S가 생성될텐데
- 생성되는 S에 중복이 있음
- 예를들어 S가 "ABC....Z"이면 중복하는 permutation이 있음
- A->A, B->B, ... Z->Z가 되는 변환
- A->B, B->A, .... Z->Z가 되는 변환
- 따라서 안되는 문자열이 있긴 있음
- 문제에서 주어진것은 "ABC...Z"가 -> 한번 -> 두번 -> "QWER....M"이 된 것임
- A==>Q==>J==>P... 와 같이 두번씩 변환된 결과를 얻을 수 있음
- 일단 잘은 모르겠지만 어떤 변환 로직이 있다고 치면
- 예를들어, A->C->K->Z->....->A, B->F->I->...->B
- 뭐 이런식으로 하나의 큰 사이클일수도 있고, 여러개의 사이클일수도 있음
- 이런 변환로직에서 "두 칸"씩 변환한 결과를 얻어볼 수 있음
- 그런데 사이클의 길이가 홀/짝일때에 따라 결과가 다름
- 사이클의 길이가 홀이면 -> 두 칸씩 변환한 결과의 길이는 홀수임
- 사이클의 길이가 짝수면 -> 두 칸씩 변환한 결과는 짝수/2 임
- 이건 그림으로 그려보면 됨 예를들어
- A->C->K->Z->P->A 일때 두칸씩 가면 A->K->P->C->Z->A, 길이 5 가 됨
- A->C->K->Z->A 이면, A->K->A, 길이 2 또는 C->Z->C, 길이 2
- 현재 알고 있는 정보는 두 칸씩 변환한 결과임(문제로부터 생성 가능)
- 만약에 사이클의 길이가 홀이면 -> 변환로직 무리 없음. 만들어 볼 수 있음
- 사이클의 길이가 짝이면 -> 애매한데?
- 4개, 4개면 => 두개 합쳐서 만들어 볼 수 있음
- 4개만 있으면 => 못만듬.
- 결국 두 칸씩 변환환 결과에서 -> 사이클을 찾고 -> 길이를 식별해서 -> 짝수인데 짝이 없으면 실패, 그외는 성공
newbieski