[BOJ 20047] 동전 옮기기

View as PDF

Submit solution

Points: 3
Time limit: 0.5s
Memory limit: 512M

Problem type
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

100 원짜리 동전과 10 원짜리 동전이 임의의 순서로 한 선 위에 나열되어 있다고 하자. 이제 여기서 ‘두 손가락 이동’ 을 아래와 같이 정의하자.

  • 단계 1: 임의의 두 동전을 선택한다.
  • 단계 2: 단계 1 에서 선택한 두 동전을 둘의 순서를 유지한 채 임의의 위치로 이동한다. (두 동전 모두 제자리에 있거나 두 동전의 순서를 유지한다면 하나만 이동해도 된다.)

‘두 손가락 이동’ 후에도 다른 동전들 간의 순서는 그대로 유지된다. 예를 들어 100 원을 o, 10 원을 x 라 했을 때, 초기에 동전이 oxoxoxxxoo 와 같이 나열되어 있다 하자. 이제 이들 중 굵게 표시된 두 동전을 선택하여 두 손가락 이동을 한번 한 경우, 나올 수 있는 여러 결과들 중에서 네 가지 결과만 아래에 표시했다 (아래 예시에 없는 다른 결과들 또한 나올 수 있음에 유의하자).

  • oxoxoxxxoo
  • oxooxxxxoo
  • oxoxoxxoxo
  • oxoxoxxxoo

n 개의 동전이 나열되어 있는 두 상태 S, T와 함께 두 손가락 이동을 위해 선택할 두 동전의 위치가 주어졌을 때, 한번의 두 손가락 이동을 통해 S에서 T로의 변환이 가능한지 결정하는 프로그램을 작성하시오.

입력 형식

입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 ST 가 각각 주어지며, 이 때 STox 로 이루어진 길이가 n 인 문자열로 표현된다 (ox 는 모두 소문자이다). 동전의 위치는 왼쪽에서 오른쪽으로 0부터 n − 1까지 차례대로 번호를 매겨 구분한다. 마지막 줄에는 두 손가락 이동을 위해 선택할 두 동전의 위치 ij가 주어지며, ij 보다 작다 (0 ≤ i < jn − 1).

출력 형식

출력은 표준출력을 사용한다. 한번의 두 손가락 이동을 통해 S 에서 T로의 변환이 가능한 경우 YES 를, 그렇지 않은 경우 NO 을 출력한다.

예제 입력 1

9
oxoxoxxxo
oxoxoxxox
4 5

예제 출력 1

YES

예제 입력 2

10
oxoxxoxxxo
ooxoxxxxox
3 4

예제 출력 2

NO

Comments

There are no comments at the moment.