📒 문제 설명
🔖 https://www.algospot.com/judge/problem/read/PICNIC
📖 문제
그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.
시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.
스위치 연결된 시계 0 0, 1, 2 1 3, 7, 9, 11 2 4, 10, 14, 15 3 0, 4, 5, 6, 7 4 6, 7, 8, 10, 12 5 0, 2, 14, 15 6 3, 14, 15 7 4, 5, 7, 14, 15 8 1, 2, 3, 4, 5 9 3, 4, 5, 9, 13
시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.
✍ 입력
첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다.
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.
💻 출력
각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1을 출력한다.
✏️ 풀이 과정
📝 1차 시도
-
어떤 스위치든 네 번을 누르게 되면 시계는 원래 상태로 돌아가게 되므로, 한 스위치를 네 번 이상 누르는 경우는 고려하지 않아도 된다. 따라서 이 문제에서 가능한 경우의 수는 4^10이다.
-
스위치를 누르는 횟수의 최솟값을 구하는 문제이므로, 스위치를 누르는 순서는 고려하지 않아도 된다.
✨ 소스 코드
import sys
input = sys.stdin.readline
switches = [
[0, 1, 2],
[3, 7, 9, 11],
[4, 10, 14, 15],
[0, 4, 5, 6, 7],
[6, 7, 8, 10, 12],
[0, 2, 14, 15],
[3, 14, 15],
[4, 5, 7, 14, 15],
[1, 2, 3, 4, 5],
[3, 4, 5, 9, 13]
]
# 총 10개의 스위치를 3번까지 누를 수 있으므로 최댓값은 30
INF = 30
def pushSwitch(clock_states, switch_num):
for clock_num in switches[switch_num]:
clock_states[clock_num] = (clock_states[clock_num] + 3) % 12 or 12
def clockSync(clock_states, switch_num):
if switch_num == len(switches):
if all(state == 12 for state in clock_states):
return 0
else:
return INF
result = INF
for i in range(4):
result = min(result, i + clockSync(clock_states, switch_num + 1))
pushSwitch(clock_states, switch_num)
return result
C = int(input())
for _ in range(C):
clock_states = list(map(int, input().split()))
result = clockSync(clock_states, 0)
print(result if result != INF else -1)교재에서 접근한 것과 크게 다르지 않았지만, 채점에서 시간 초과가 발생했다. 같은 방식을 C++로 작성하여 제출하니 정답 처리되었다.
📝 2차 시도
- 11번, 12번, 13번 시계는 각각 1번, 4번, 9번 스위치에만 연결되어 있다. 즉, 11번 ~ 13번 시계를 12시로 맞추기 위해서는 반드시 1번, 4번, 9번 스위치를 작동시켜야 하며, 이 스위치들만
prior_switches로 따로 빼두어priorPush함수로 먼저 작동시켰다.
✨ 소스 코드
import sys
input = sys.stdin.readline
prior_switches = [
[3, 7, 9, 11],
[6, 7, 8, 10, 12],
[3, 4, 5, 9, 13]
]
switches = [
[0, 1, 2],
[4, 10, 14, 15],
[0, 4, 5, 6, 7],
[0, 2, 14, 15],
[3, 14, 15],
[4, 5, 7, 14, 15],
[1, 2, 3, 4, 5]
]
INF = 30
def pushSwitch(clock_states, switch_list, switch_num):
for clock_num in switch_list[switch_num]:
clock_states[clock_num] = (clock_states[clock_num] + 3) % 12 or 12
def priorPush():
prior_count = 0
if clock_states[11] != 12:
i = (12 - clock_states[11]) // 3
prior_count += i
if i != 0:
for _ in range(0, i):
pushSwitch(clock_states, prior_switches, 0)
if clock_states[12] != 12:
i = (12 - clock_states[12]) // 3
prior_count += i
if i != 0:
for _ in range(0, i):
pushSwitch(clock_states, prior_switches, 1)
if clock_states[13] != 12:
i = (12 - clock_states[13]) // 3
prior_count += i
if i != 0:
for _ in range(0, i):
pushSwitch(clock_states, prior_switches, 2)
return prior_count
def clockSync(clock_states, switch_num):
if switch_num == len(switches):
if all(state == 12 for state in clock_states):
return 0
else:
return INF
result = INF
for i in range(4):
result = min(result, i + clockSync(clock_states, switch_num + 1))
pushSwitch(clock_states, switches, switch_num)
return result
C = int(input())
for _ in range(C):
clock_states = list(map(int, input().split()))
result = priorPush() + clockSync(clock_states, 0)
print(-1 if result >= INF else result)🤔 다시 생각해 볼 것
- 2차 시도에서는 Python으로도 시간 초과가 발생하지 않았지만, 출제 의도가 4^10의 완전 탐색이라면 다른 방법으로 접근해야 할 것 같다.
- 연립 방정식을 사용한 풀이가 가장 빠르다고 하는데, 추후에 다시 시도해봐야 겠다.
