[SWEA]230216 문제풀이

배열 최소 합

T = int(input())
for i in range(T):
    N = int(input())
    lst = []
    for j in range(N):
        lst.append(list(map(int, input().split())))
    ans = 1e10
 
    def makesum(n, s, v):
        global ans
        temp = v + [n]
        if len(temp) == N and s < ans:
            ans = s
        else:
            for j in range(N):
                if j not in temp and s + lst[len(temp)][j] < ans:
                    makesum(j, s + lst[len(temp)][j], temp)
    for k in range(N):
        makesum(k, lst[0][k], [])
    print(f'#{i+1} {ans}')

재귀를 돌릴 때 각 케이스에서 방문 목록을 어떻게 처리할지가 관건인 문제였는데, 방문 목록 처리할 아이디어가 생각나지 않아 그냥 방문한 좌표 x값을 하나씩 append 하는 식으로 해결했다.

토너먼트 카드게임

T = int(input())
for i in range(1, T+1):
    N = int(input())
    lst = list(map(int, input().split()))
    for j in range(N):
        lst[j] = (lst[j], j+1)
 
    def winner(l):
        if len(l) == 1:
            return l[0]
        elif len(l) == 2:
            if l[0][0] - l[1][0] in [-2, 1]:
                return l[0]
            elif l[0][0] - l[1][0] in [-1, 2]:
                return l[1]
            elif l[0][0] - l[1][0] == 0:
                return l[0]
        else:
            l1winner = winner(l[:(len(l)-1)//2+1])
            l2winner = winner(l[(len(l)-1)//2+1:])
            return winner([l1winner, l2winner])
 
    print(f'#{i} {winner(lst)[1]}')

또 인덱스땜에 시간 엄청 잡아먹은 문제... 문제에 인덱스 조건이 그대로 나와있는데도 한참을 헤맸다. 분할 정복할 때 밑에서부터 올라오는 값들의 원래 인덱스 값을 알기 위해서 처음부터 인덱스와 함께 튜플로 저장했다.

재미있는 오셀로 게임

dy = [-1, -1, -1, 0, 0, 1, 1, 1]
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
T = int(input())
for i in range(1, T+1):
    N, M = map(int, input().split())
    board = [[0] * N for _ in range(N)]
    # 초기 돌 셋팅
    wy = wx = N//2
    board[wy][wx] = board[wy - 1][wx - 1] = 2
    board[wy - 1][wx] = board[wy][wx - 1] = 1
    # 돌 두기
    for j in range(M):
        x, y, c = map(int, input().split())
        # 좌표 보정
        x -= 1
        y -= 1
        board[y][x] = c
        for delta in range(8):
            # 보드 내 확인
            if y + dy[delta] in range(N) and x + dx[delta] in range(N):
                # 다른색 돌 여부 확인
                if board[y + dy[delta]][x + dx[delta]] == abs(c - 3):
                    cnt = 0
                    # 한 방향으로 진행, 카운트 저장
                    while True:
                        # 다음 돌이 다른색이고 그 다음 넘어갈 칸이 있을 때 카운트++ 진행
                        if board[y + dy[delta]*(cnt+1)][x + dx[delta]*(cnt+1)] == abs(c - 3):
                            cnt += 1
                            if y + dy[delta]*(cnt+1) in range(N) and x + dx[delta]*(cnt+1) in range(N):
                                continue
                            else:
                                cnt = 0
                                break
                        elif board[y + dy[delta]*(cnt+1)][x + dx[delta]*(cnt+1)] == c:
                            break
                        else:
                            cnt = 0
                            break
                    # 카운트만큼 칸 색칠
                    if cnt:
                        for flip in range(cnt):
                            board[y + dy[delta] * (flip + 1)][x + dx[delta] * (flip + 1)] = c
 
    # 돌 세기
    black = 0
    white = 0
    for yy in range(N):
        for xx in range(N):
            if board[yy][xx] == 1:
                black += 1
            elif board[yy][xx] == 2:
                white += 1
 
    print(f'#{i} {black} {white}')

앞의 짜증나는 문제들을 풀고나니 선녀처럼 다가왔던 문제... 델타를 8개 쓰는 발상이 바로 떠올라야 하고 한방향으로 직진하면서 뒤집을지 여부를 결정하는 것만 해결하면 됐다. 주석이랑 변수명 설정에 조금 신경쓰면서 풀었는데, 진짜로 재미는 있던 문제였다.