27921번 - 동전 퍼즐 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 493 | 278 | 246 | 56.422% |
문제
동전 퍼즐을 풀어 보자! 처음에 무한 격자 평면에 동전 몇 개가 놓여 있다. 모든 동전은 격자점 위에 있다.
퍼즐의 목표는 최소 개수의 동전을 옮겨서 새로운 모양을 만드는 것이다. 동전을 옮길 때는 한 번에 한 개씩, 동전을 들어서 빈 격자점에 놓으면 된다. 새로운 모양이 만들어지는 위치는 어디든 상관없지만, 회전된 모양이나 대칭된 모양을 만드는 것은 인정되지 않는다.
예를 들어, 다음과 같은 두 가지 동전의 배치를 생각하자.
첫 번째 배치에서 두 번째 배치로 만들기 위해서는 아래와 같이 최소 네 개의 동전을 옮겨야 한다.
현재 동전의 배치와 만들어야 하는 동전의 배치가 주어질 때, 옮겨야 하는 동전의 개수는 최소 몇 개인지 구하시오.
입력
첫 번째 줄에 정수 $H_1$, $W_1$이 주어진다. ($1\le H_1,W_1\le 10$)
그다음 줄부터 $H_1$개의 줄에 길이 $W_1$의 문자열이 주어진다. ‘.’은 빈칸, ‘O’는 동전이 있는 칸이다. 현재 동전의 배치를 나타낸다.
그다음 줄에 정수 $H_2$, $W_2$가 주어진다. ($1\le H_2,W_2\le 10$)
그다음 줄부터 $H_2$개의 줄에 길이 $W_2$의 문자열이 주어진다. ‘.’은 빈칸, ‘O’는 동전이 있는 칸이다. 만들어야 하는 동전의 배치를 나타낸다.
두 배치의 동전의 개수는 동일함이 보장된다.
출력
옮겨야 하는 동전의 최소 개수를 출력한다.
예제 입력 1
5 5 O...O O...O OOOOO ..O.. ..O.. 5 5 ..O.. ..O.. OOOOO O...O O...O
예제 출력 1
4
예제 입력 2
2 5 OOO.O O.OOO 4 3 .OO OO. .OO OO.
예제 출력 2
4
예제 입력 3
3 5 .O... OO... ..... 4 3 ... ... ..O .OO
예제 출력 3
0
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호