[Python] SWEA 5188: 최소합, 5189: 전자카트

5188 최소합

첫 번째 시도

dx = [0,1]
dy = [1,0]

def ans(tmp_list, k, startx, starty):
    global ans_sum
    sumV = arr[startx][starty]
    for i in range(k):
        newx = dx[tmp_list[i]] + startx
        newy = dy[tmp_list[i]] + starty
        sumV += arr[newx][newy]
        if sumV > min(res):
            return
        else: #최대값을 넘어버린 경우...
            startx = newx
            starty = newy
    res.append(sumV)
    return

def per(i, k):
    if i == k:
        # print(tmp)
        if sum(tmp) == k//2:
            ans(tmp, k, 0, 0)
    else:
        for j in range(2):
            if visit[j] == 0:
                tmp.append(j)
                per(i + 1, k)
                tmp.pop()

T = int(input())
for t in range(1, T + 1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    tmp = []
    res = [9999999]
    ans_sum =999999999
    visit = [False] * 2
    sumV = arr[0][0]
    per(0,(N-1)*2)
    print(f'#{t} {min(res)}')

답은 잘 나왔지만 시간 초과가 나왔다. 나름 단순하게... 단순하게 접근하려고 했다. 부분집합을 만든 후 그 부분집합의 sum 값이 집합 길이의 절반인 경우(만든 부분집합에 0과 1만 존재하기 때문에)에만 합을 구하려고 했으나... 시간 초과가 걸리기도 했고 코드가 너무 지저분하다는 생각이 들었다. 애초에 부분집합을 구할 때 visited 이용하는 것이 아니기도 하고!

ANS

dir = ([0,1],[1,0])

def brute_force(x,y,sumV):
    global ans_sum
    sumV += arr[x][y]
    if x==N-1 and y==N-1:
        if sumV < ans_sum:
            ans_sum = sumV
        return
    elif ans_sum<sumV:
        return
    for d in dir:
        dx = d[0]
        dy = d[1]
        nx = dx + x
        ny = dy + y
        if nx<N and ny<N:
            brute_force(nx,ny,sumV)

T = int(input())
for t in range(1, T + 1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    tmp = []
    ans_sum =999999999
    brute_force(0,0,0)
    print(f'#{t} {ans_sum}')

답안 코드. 훨씬 깔끔해... 남들이 봐도 그렇구나~ 할만한 코드 짜는 게 정말 어려운 거 같다. 그냥 제한 조건만 잘 걸어준다면 재귀로 깔끔하게 풀리는 문제.

 

5189 전자카트

ANS

T = int(input())

def dfs(current, tmp):
    global res
    if tmp < res:
        if 0 not in visited[1:]:  # 전부 방문했다면
            res = min(res, tmp + a[current][0])  # 결과값 갱신하고 함수 종료
            return
        for next in range(1, N):
            if a[current][next] != 0 and visited[next] == 0:
                visited[next] = 1
                dfs(next, tmp + a[current][next])
                visited[next] = 0


for tc in range(1, T+1):
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]

    res = 99999999
    for i in range(1, N):
        visited = [0] * N
        visited[i] = 1
        dfs(i, a[0][i])
    print(f'#{tc} {res}')