티스토리 뷰

Coding Test/알고스팟

[C++] 알고스팟/완전탐색 - Synchronizing Clocks

Junchoi 2020. 1. 18. 11:18

문제 링크

https://algospot.com/judge/problem/read/CLOCKSYNC

 

algospot.com :: CLOCKSYNC

Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들

algospot.com

 

0번부터 9번까지의 스위치를 0~3번씩 누르는 모든 경우의 수를 완전탐색으로 모든 시계가 12시가 되는 최소 버튼의 수를 구합니다. 스위치를 4번 누르는 것은 한 바퀴를 도는 것이기 때문에 스위치마다 최대 3번 이상은 누르지 않아도 되기 때문입니다.

이 경우 4^10 = 1048576개의 경우의 수가 나오기 때문에 제한 시간안에 모든 경우의 수를 탐색해볼 수 있습니다.

 

 

구현 코드

 

'Coding Test > 알고스팟' 카테고리의 다른 글

[C++] 알고스팟/분할정복 - 쿼드 트리 뒤집기  (0) 2020.03.30
[C++] 알고스팟/비트마스크 - 졸업 학기  (0) 2020.03.29
[C++] 알고스팟/완전탐색 - 게임판 덮기  (0) 2020.01.11
[C++] 알고스팟/완전탐색 - 소풍  (0) 2020.01.10
[C++] 알고스팟/유클리드 - 마법의 약  (0) 2020.01.08