6.8 문제 : 시계 맞추기(Python)

문제 출처 : algospot.com :: CLOCKSYNC

algospot.com :: CLOCKSYNC

---

1. 내가 생각한 풀이

INF = int(1e9)

switch = [
    [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]
]

def check(data):
    isEnd = True

    for i in range(16):
        if data[i] != 12:
            isEnd = False

    return isEnd
    
 def click(data, num_click)
    if check(data):
	return num_click
        
    result = INF

    for i in range(10):
       for j in switch[i]:
           data[j] += 3
           if data[j] > 12:
               data[j] -= 12

       candid = click(data, num_click + 1)
       result = min(result, candid)

       for j in switch[i]:
           data[j] -= 3
           if data[j] <= 0:
               data[j] += 12

(1) 클릭 횟수를 매개변수로 지정

• 기저 사례는check() 함수가 True일 때(모든 시계가 12시를 가리킬 때) 반환하도록 함

(2) 10개의 스위치를 한 번씩 누를 때 재귀 호출을 반복

2. 틀린 이유

• 클릭 수를 기준으로 할 경우 재귀 호출 깊이 한도를 초과하는 문제가 발생

---

2. 해설 풀이 방법

def check(data):
    isEnd = True

    for i in range(16):
        if data[i] != 12:
            isEnd = False

    return isEnd

def push(data, num_switch):
    for i in switch[num_switch]:
        data[i] += 3
        if data[i] > 12:
            data[i] -= 12
            
# 0번 스위치 부터 9번 스위치까지 눌러보면서 하나의 스위치가 몇 번씩 눌렸는지 누적함
def click(data, num_switch):
    if num_switch == 10:
        if check(data):
            return 0
        else:
            return INF

    result = INF
    
    # 모든 스위치는 4번 누르면 처음 상태로 돌아간다.
    # i가 스위치를 누른 횟수를 저장함(어떤 스위치든 최대 3번까지 누를 수 밖에 없다.)
    for i in range(4):
        result = min(result, i + click(data, num_switch + 1))
        push(data, num_switch)

    return result
    
# 문제 입-출력
for tc in range(int(input())):
    data = list(map(int, input().split())) # 시계들의 초기 상태 입력

    print(click(data, 0))

 

3. 해설

(1) 클릭 수가 아닌 스위치 번호를 매개 변수로 활용

• 0번 스위치부터 9번 스위치까지 차례로 누르며 마지막 스위치까지 누른 이후에 시계를 검사
• 변수 i : 어떤 스위치를 누른 횟수를 저장
• return을 0을 하지만 마지막 반복문에서 'i + click(data, num_switch + 1)'에서 변수 i를 통해 누른 횟수를 누적하게 된다.

(2) 하나의 스위치는 최대 3번까지만 누를 필요가 있다.

• 스위치를 4번 누르게 되면 결국 초기 상태와 같아진다.
• 마지막 반복문에서 결국 처음 상태로 돌리는 (재귀 호출 전 설정한 값을 되돌리는) 결과가 나타난다.

---

4. 후기

  문제를 푸는 큰 그림은 얼추 생각할 수 있었지만 나는 재귀호출에 사용되는 매개변수를 클릭 횟수로 설정했던 것과 스위치를 4번 누르면 결국 처음 상태로 돌아가는 것을 생각하지 못 했다. 즉, 문제를 읽고 그대로 생각하는 것 보다는 문제에서 나타날 수 있는 특징을 파악하지 못 했다.

  그리고 솔직히 기저 사례에서 return 0을 하는 것은 전혀 생각도 못 했는데 재귀 호출 단계에서 그 값을 누적 시키는 것이 정말 기발한 방법으로 느껴졌다. 하지만 return 0을 하니까 누적된다는 것이 직관적으로 느껴지지는 않았다. 마지막 반복문을 잘 보면 어떤 스위치에 대해서 push()함수를 나중에 실행하므로 결과적으로 누르는 횟수가 최대 3회까지만 누적 되는 것이 맞지만(반복문이 끝나면 스위치는 4번 누른다.) 한 번 딱 코드를 보면서 바로 이해하기는 쉽지가 않았다.

  그래도 앞의 문제부터 차례로 문제들을 풀면서 아주아주 희미하게나 재귀 호출을 통한 풀이 방법에 대해 구성 방법을 알아가게 되었다고 생각한다.

---

github : Algorithmic_Problem_Soving_Strategies/q3_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies