[BOJ 20047] 동전 옮기기
View as PDF100 원짜리 동전과 10 원짜리 동전이 임의의 순서로 한 선 위에 나열되어 있다고 하자. 이제 여기서 ‘두 손가락 이동’ 을 아래와 같이 정의하자.
- 단계 1: 임의의 두 동전을 선택한다.
- 단계 2: 단계 1 에서 선택한 두 동전을 둘의 순서를 유지한 채 임의의 위치로 이동한다. (두 동전 모두 제자리에 있거나 두 동전의 순서를 유지한다면 하나만 이동해도 된다.)
‘두 손가락 이동’ 후에도 다른 동전들 간의 순서는 그대로 유지된다. 예를 들어 100 원을 o, 10 원을 x 라 했을 때, 초기에 동전이 oxoxoxxxoo 와 같이 나열되어 있다 하자. 이제 이들 중 굵게 표시된 두 동전을 선택하여 두 손가락 이동을 한번 한 경우, 나올 수 있는 여러 결과들 중에서 네 가지 결과만 아래에 표시했다 (아래 예시에 없는 다른 결과들 또한 나올 수 있음에 유의하자).
oxoxoxxxoooxooxxxxoooxoxoxxoxooxoxoxxxoo
n 개의 동전이 나열되어 있는 두 상태 S, T와 함께 두 손가락 이동을 위해 선택할 두 동전의 위치가 주어졌을 때, 한번의 두 손가락 이동을 통해 S에서 T로의 변환이 가능한지 결정하는 프로그램을 작성하시오.
입력 형식
입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T 는 o 와 x 로 이루어진 길이가 n 인 문자열로 표현된다 (o 와 x 는 모두 소문자이다). 동전의 위치는 왼쪽에서 오른쪽으로 0부터 n − 1까지 차례대로 번호를 매겨 구분한다. 마지막 줄에는 두 손가락 이동을 위해 선택할 두 동전의 위치 i와 j가 주어지며, i는 j 보다 작다 (0 ≤ i < j ≤ n − 1).
출력 형식
출력은 표준출력을 사용한다. 한번의 두 손가락 이동을 통해 S 에서 T로의 변환이 가능한 경우 YES 를, 그렇지 않은 경우 NO 을 출력한다.
예제 입력 1
9
oxoxoxxxo
oxoxoxxox
4 5
예제 출력 1
YES
예제 입력 2
10
oxoxxoxxxo
ooxoxxxxox
3 4
예제 출력 2
NO
Comments