https://www.acmicpc.net/problem/21873
요약
- 양쪽에 n 개씩 검은 개구리, 흰 개구리가 있음
- 일정한 규칙을 준수하며 서로의 위치를 바꾸는 방법을 출력
- 빈칸으로 한칸 움직이거나
- 색깔이 다른 개구리를 뛰어넘어 빈 칸으로 움직이거나
접근법
- 다른분들 풀이를 보면 규칙을 찾아서 적용한 것 같으나, 일단 다르게 접근함
- 5개정도까지 손으로 해봄
- 편의상 왼쪽을 1번 개구리들, 오른쪽을 2번개구리들이라고 하면
- 다음의 규칙을 찾았음
- 잘은 모르겠지만 처음은 1이동, 2이동, 2이동을 해야함
- 개구리를 빈칸으로 이동시켰을때 연속 두개로 같은 개구리로 만들어지면 안됨 => 번갈아서 나타나야함
- 규칙을 준수하도록 이동하도록 구현함
- 배열에 -5, -4 ,.... 0 ... 4, 5와 같이 개구리 번호를 기록
- 빈 공간의 위치를 기억 : 빈 공간으로 어떤 색깔의 개구리가 올지를 판단하기 위함임
- 채워야하는 끝 위치를 기억 : l, r
- 처음에는 1, 2, 2로 이동하고
- 다음번에 이동시켰을때 연속 두개로 같은 개구리가 나오면 이동시키지 않음 ==> 빈 공간의 왼쪽/오른쪽이 어떤 색깔로 채워져있는지로 판단함
추가 구현
- 3까지는 잘 되는 것 같은데 4부터 안됨
- 손으로 해보니 1번 개구리들을 쭉 이동시키고, 2번 개구리들을 쭉 이동시키고, .... 로 해야함 : 1/2/1/2... 번갈아 배치를 만족시켜야함
- 즉 빈 공간이 있을때 먼저 이동하는 우선순위는 이전까지 이동했던 개구리들임
- 이를 위해 이전까지 어떤 개구리를 이동했는지를 기록하고, 이에따라 이동 우선순위를 부여해서 구현함
newbieski