고고학 최고의 발견 (131702번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/131702

프로그래머스

 

프로그래머스 - 고고학 최고의 발견 (131702번)

 

난이도 : Lv 3

알고리즘 : Simulation

풀이 소요 시간 : 50분

Time Complexity : O( (4^N) * (N^2) ) 

 

from itertools import product
from copy import deepcopy
import sys


def solution(clockHands):
    answer = sys.maxsize
    n = len(clockHands)
    dr, dc = [1, 0, -1, 0, 0], [0, 1, 0, -1, 0]
    # 1
    for case in product(range(4), repeat=n):
        cur = 0
        board = deepcopy(clockHands)
        for c in range(n):
            if not case[c]:
                continue
            cur += case[c]
            for rr, cc in zip(dr, dc):
                if 0 <= rr < n and 0 <= c+cc < n:
                    board[rr][c+cc] = (board[rr][c+cc] + case[c]) % 4
        # 2
        for r in range(1, n):
            for c in range(n):
            	# 3
                dgr = (4-board[r-1][c]) % 4
                if not dgr:
                    continue
                cur += dgr
                for rr, cc in zip(dr, dc):
                    if 0 <= r+rr < n and 0 <= c+cc < n:
                        board[r+rr][c+cc] = (board[r+rr][c+cc] + dgr) % 4
        # 4
        if any(board[-1]):
            continue
        answer = min(cur, answer)  # 4

    return answer

 

아이디어 떠올리기와 구현이 꽤 까다로운 문제였다.

 

1. 먼저 암호의 첫째 줄에, 시계 바늘을 바꿀 수 있는 모든 경우의 수를 적용한다.

 

그리고 각 경우마다,

 

2. 둘째 줄부터 시작해서 각 줄마다 한 칸씩 오른쪽으로 이동하면서

 

3. 바로 윗 칸의 바늘이 12시가 되도록 만들기 위해 돌려야 하는 횟수를 더해준다. (cur 에 더해줌)

 

위의 2, 3번 과정을 마지막 줄까지 다 진행하면,

 

4. 마지막 줄의 값들이 모두 0인지 확인하고 (즉, 모두 시계바늘이 12시를 향하는지 확인)

만약 그렇다면, 현재까지 기록된 최솟값 (answer) 과 비교해서

더 작으면 최솟값 (answer) 을 현재 값 (cur) 으로 업데이트 한다.