60059606160062(プログラマー)

アルゴリズム自体は難しくありませんが、直接実現するのに時間がかかります.


解けたけど効率があまりよくないようです.ほほほ
📋コード#コード#

# 자물쇠 영역의 합이 n*n이라면 정답.
# 한 구역이라도 2이상이면 돌기가 겹치는 것 이므로 건너뛴다.
def sum_check(key_board,board,n,m):
    sum = 0
    for i in range(0,n):
        for d in range(0,n):
            if board[i+m-1][d+m-1] + key_board[i+m-1][d+m-1] >= 2:
                return False
            else:
                sum += board[i+m-1][d+m-1] + key_board[i+m-1][d+m-1]
    if sum == n*n:
        return True
    else:
        return False

#0, 90, 180, 270도 바꿔가며 sum_check함수를 호출한다
def check(key_board,board,n,m):
    if sum_check(key_board,board,n,m)==True:
        return True
    for _ in range(3):
        tmp_keyboard = list([0]*(n+2*m-2) for _ in range(n+2*m-2))
        #90도 회전
        for i in range(n+2*m-2):
            for d in range(n+2*m-2):
                tmp_keyboard[d][n+2*m-3-i] = key_board[i][d]
        if sum_check(tmp_keyboard,board,n,m)==True:
            return True
        else: key_board=list(tmp_keyboard)
    return False

def solution(key, lock):
    n = len(lock)
    m = len(key)
    # n+2*m-2크기의 board를 생성한다
    board = list([0]*(n+2*m-2) for _ in range(n+2*m-2))

    # 자물쇠를 보드의 가운데에 위치시킨다
    for i in range(0,n):
        for d in range(0,n):
            board[i+m-1][d+m-1]=lock[i][d]

    # 열쇠를 맨위왼쪽부터 이동시켜가며 체크한다
    for i in range(n+m-1):
        for d in range(n+m-1):
            key_board = list([0]*(n+2*m-2) for _ in range(n+2*m-2))
            for x in range(m):
                for y in range(m):
                    key_board[i+x][d+y] = key[x][y]
            
            if check(key_board,board,n,m) == True:
                return True
            else: 
                continue
    return False
                    

60061(プログラマ)柱梁取付
📌質問リンク
https://programmers.co.kr/learn/courses/30/lessons/60061
💡 問題を解く

#설치 가능한지 검사 (d가 true면 삭제가능한지 검사)
def check(x,y,a,board,delete):
    if delete==True and board[x][y][a]==False:
        return True
    if a==0: #기둥
        #바닥면이거나, 기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
        if y==0 or board[x][y-1][0] or (x!=0 and board[x-1][y][1]) or board[x][y][1]:
            return True
    elif a==1: #보
        #기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
        if board[x][y-1][0] or board[x+1][y-1][0] or ((x!=0 and board[x-1][y][1]) and board[x+1][y][1]):
            return True
    return False

def solution(n, build_frame):
    # board[][]의 첫 원소는 기둥, 두번째 원소는 보를 의미
    board = list([list([False,False]) for _ in range(n+1)] for _ in range(n+1))
    
    for x,y,a,b in build_frame:
        if b==0: #삭제일 경우
            board[x][y][a] = False
            if a==0:
                if not(check(x,y+1,0,board,True) and check(x,y+1,1,board,True) and check(x-1,y+1,1,board,True)):
                    board[x][y][a] = True
                    continue
            elif a==1:
                if not(check(x,y,0,board,True) and check(x+1,y,0,board,True) and check(x-1,y,1,board,True) and check(x+1,y,1,board,True)):
                    board[x][y][a] = True
                    continue
        elif b==1: #설치일 경우
            if a==0: #기둥
                #바닥면이거나, 기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
                if check(x,y,a,board,False):
                    board[x][y][0]=True
            elif a==1: #보
                #기둥위에 있거나, 보의 끝 부분 위에 있을 경우 가능
                if check(x,y,a,board,False):
                    board[x][y][1]=True       
    answer = []
    for i in range(n+1):
        for d in range(n+1):
            if board[i][d][0]==True:
                answer.append([i,d,0])
            if board[i][d][1]==True:
                answer.append([i,d,1])
    return answer

from itertools import permutations


def solution(n, weak, dist):
    weak_length = len(weak)
    # 배열을 두배 늘려주면 방향 고민할 필요 없다
    for i in range(weak_length):
        weak.append(weak[i] + n)

    answer = int(1e9)  # 점검 불가능한 경우 가정
    dist_order = list(map(list, permutations(dist, len(dist)))) 
    for i in range(weak_length):
        # 시작점을 하나씩 바꾸면서, weak의 길이만큼 잘라서 사용
        start = [weak[j] for j in range(i, i + weak_length)]
        for order in dist_order:  # 탐색
            result = 1  # 친구 활용 개수
            check_len = start[0] + order[result - 1]  # 첫번째 친구가 확인할 수 있는 최대 거리
            for k in range(weak_length):
                if start[k] > check_len:  # 확인가능한 최대거리를 넘은 경우
                    result += 1  # 활용되는 dist의 친구 수 추가
                    # 더 이상 투입 인원이 없는 경우
                    if result > len(order):
                        break
                    # 다음 친구가 확인할 수 있는 거리 업데이트
                    check_len = start[k] + order[result - 1]

            answer = min(answer, result)

    if answer > len(dist):
        return -1
    return answer