졍's 기술 블로그

근손실

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.

다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트로 간주한다. 각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.

대학원생은 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고자 한다. 1일차부터 N일차까지의 모든 기간동안, 어떤 시점에서라도 중량이 500보다 작아지지 않도록 해야 한다.

예를 들어 N=3, K=4일 때, 각 운동 키트의 중량 증가량이 다음과 같다고 가정하자.

이 때 1번, 3번, 2번 순서대로 운동 키트를 적용한다고 해보자. 이 경우 운동 1일차에 대학원생은 중량이 3만큼 증가하지만 그와 동시에 하루에 중량이 4만큼 감소하기 때문에, 1일이 지난 이후에 중량은 499가 된다. 따라서 조건을 만족하지 못한다.

반면에 3번, 1번, 2번 순서대로 운동 키트를 적용한다고 해보자. 그러면 1일차부터 운동을 모두 마친 날까지의 모든 시점에 대하여 항상 중량이 500이상이 된다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 1개씩의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력하는 프로그램을 작성하시오.

위 예시에서는 모든 경우 중에서 총 4가지 경우가 조건을 만족한다.

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

예제 입출력

Algorithm

Back Tracking
1. stack에 운동 키트 추가
    ☞ stack에 들어있지 않은 숫자만 추가
2. 운동 키트 적용 직후 중량 갱신
3. 재귀함수 호출
4. 재귀함수 return되면 중량 원상복구 후 pop
5. stack의 길이가 N이 되거나 중량이 500 미만이 되면 pop먼저 할 수 있도록 구현

Code

def back_tracking(now_weight):
    global answer
    
    # stack의 길이가 N이 되거나 중량이 500 미만이 되면 POP먼저 하도록 구현
    if len(stack) == N or now_weight < 500:
        pass
    else:
        for idx in range(N):
            if idx not in stack:
                stack.append(idx)
                # 중량 계산
                now_weight = now_weight - K + weights[idx]
                # 마지막 index이고 중량이 500이상이면 answer 증가
                if len(stack) == N and now_weight >= 500:
                    answer += 1
                back_tracking(now_weight)
                stack.pop()
                now_weight = now_weight + K - weights[idx]

N, K = map(int, input().split())
weights = list(map(int, input().split()))
stack = []
global answer
answer = 0
now_weight = 500
back_tracking(now_weight)
print(answer)

메모리: 30840 KB
시간: 176 ms

부분수열의 합

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입출력

Algorithm

Back Tracking
1. stack에 수열의 숫자 하나씩 추가
1.1. stack이 비어있으면 바로 append
1.2. stack이 비어있지 않으면 stack의 마지막 숫자보다 큰 숫자만 추가
2. stack 원소의 합이 S가 되면 ANSWER 1 증가
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 N이 되면 바로 append하지 못하도록 구현

Code

def back_tracking(sum_):
    global answer
    
    # stack 길이가 N이 되면 POP먼저 하도록 구현
    if len(stack) == N:
        pass
    else:
        for idx in range(N):
            # stack 비어있으면 바로 append
            if not stack:
                stack.append(idx)
                sum_ += list_[idx]
                if sum_ == S:
                    answer += 1
                back_tracking(sum_)
                stack.pop()
                sum_ -= list_[idx]
                
            # stack 비어있지 않으면 들어있지 않은 숫자만 추가
            elif stack[-1] < idx:
                stack.append(idx)
                sum_ += list_[idx]
                if sum_ == S:
                    answer += 1
                back_tracking(sum_)
                stack.pop()
                sum_ -= list_[idx]
                
N, S = map(int, input().split())
list_ = list(map(int, input().split()))

global answer
answer = 0
sum_ = 0
stack = []
back_tracking(sum_)
print(answer)

메모리: 30840 KB
시간: 1936 ms

로또

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 조합론, 백트래킹, 재귀

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. 입력받은 수를 리스트로 저장
2. 리스트에 들어있는 숫자를 stack에 append
2.1. stack이 비어있으면 숫자 바로 추가
2.2. stack이 비어있지 않으면 stack의 마지막 숫자보다 큰 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 stack pop
5. stack의 길이가 6이 되면 print

Code

def back_tracking():
    
    # stack의 길이가 6이 되면 print
    if len(stack) == 6:
        print(' '.join(list(map(str, stack))))
    else:
        for index in range(1, nums[0]+1):
            # stack 비어있으면 숫자 바로 추가
            if not stack:
                stack.append(nums[index])
                back_tracking()
                stack.pop()
            elif nums[index] > stack[-1]:
                stack.append(nums[index])
                back_tracking()
                stack.pop()

while True:
    nums = list(map(int, input().split()))
    if nums[0] == 0:
        break
    stack = []
    back_tracking()
    print()

메모리: 30840 KB
시간: 76 ms

외판원 순회 2

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹, 외판원 순회 문제

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. 입력으로 리스트로 저장해 graph 구현
2. stack에 값 추가
2.1. stack이 비어있으면 현재 숫자 바로 추가
2.2. stack이 비어있지 않으면 stack에 들어있지 않으면서 비용이 0 이상인 값만 추가
3. 재귀함수 호출
4. 재귀함수 호출되면 stack pop
5. stack의 길이가 N이 되면 시작지점으로 돌아올 수 있는지(비용이 0 이상인지) 확인
5.1. 시작지점으로 돌아올 수 있다면 최소비용 갱신

Code

def back_tracking(costs):
    global answer
    
    # stack의 길이가 N-1이 되면
    if len(stack) == N:
        # 시작지점으로 돌아올 수 있으면 최소 비용 갱신
        if graph[stack[-1]][stack[0]] > 0:
            costs += graph[stack[-1]][stack[0]]
            if answer > costs:
                answer = costs

    else:
        for num in range(N):
            # stack이 비어있으면
            if not stack:
                if num == 1:
                    return
                # 그냥 추가
                stack.append(num)
                back_tracking(costs)
                stack.pop()
            # stack이 비어있지 않으면 stack에 들어있지 않으면서 비용이 0 이상인 값만 추가
            elif num not in stack and graph[stack[-1]][num] > 0:
                stack.append(num)
                costs += graph[stack[-2]][stack[-1]]
                back_tracking(costs)
                costs -= graph[stack[-2]][stack[-1]]
                stack.pop()
                
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

global answer
answer = 1000000*N*N
stack = []
costs = 0
back_tracking(costs)
if answer == 1000000*N*N:
    print(0)
else:
    print(answer)

메모리: 30840 KB
시간: 1360 ms

차이를 최대로

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. stack에 포함되어있지 않은 index append
2. 재귀함수 호출
3. 재귀함수 return되면 pop
4. stack의 길이가 N이 되면 식의 최댓값 갱신

Code

def back_tracking():
    global answer
    
    # stack의 길이가 N이 되면 식의 최댓값 갱신
    if len(stack) == N:
        sum_ = 0
        for idx in range(1, N):
            sum_ += abs(nums[stack[idx-1]] - nums[stack[idx]])
        if answer < sum_:
            answer = sum_
    else:
        for index in range(N):
            if index not in stack:
                stack.append(index)
                back_tracking()
                stack.pop()
                
N = int(input())
nums = list(map(int, input().split()))

global answer
answer = 0
stack = []
back_tracking()
print(answer)

메모리: 30864 KB
시간: 200 ms

모든 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. stack이 비어있으면 숫자 바로 append
2. stack이 비어있지 않으면 stack에 포함되어있지 않은 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 N이 되면 stack print

Code

# 입력
data = list(map(int, input().split()))

# 입력 값 Dictionary에 저장 (key: 입력 값, value: 횟수)
dict_ = {}def back_tracking():
    
    # stack의 길이가 N이 되면 print
    if len(stack) == N:
        print(' '.join(list(map(str, stack))))
    else:
        for num in range(1, N+1):
            # stack 비어있으면 바로 추가
            if not stack:
                stack.append(num)
                back_tracking()
                stack.pop()
            # stack이 비어있지 않으면 stack에 없는 숫자만 append
            elif num not in stack:
                stack.append(num)
                back_tracking()
                stack.pop()
                
N = int(input())
stack = []
back_tracking()
for i in data:
    if i not in dict_:
        dict_[i] = 1
    else:
        dict_[i] += 1

flag = False # 같은 숫자가 있는 경우 False, 모두 다른 경우 True
for key, value in dict_.items():
    if value == 3:
        print(10000 + key * 1000)
        flag = False
        break
    elif value == 2:
        print(1000 + key * 100)
        flag = False
        break
    else:
        flag = True

if flag:
    print(max(dict_.keys()) * 100)

메모리: 30864 KB
시간: 216 ms

부등호

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입출력

Algorithm

back tracking - 재귀
1. 0부터 9까지 stack에 추가
1.1. stack이 비어있으면 바로 append
1.2. stack이 비어있지 않으면 stack이 없는 값이며 부등호를 확인해 < 이면 stack[-1]보다 큰 값, > 이면 stack[-1]보다 작은 값만 추가
2. 재귀함수 호출
3. 재귀함수 return되면 pop
4. stack의 길이가 K+1이 되면 최댓값, 최솟값 갱신

Code

def back_tracking():
    global min_
    global max_

    # stack의 길이가 k+1이 되면
    if len(stack) == k+1:
        num = int(''.join(list(map(str, stack))))
        # 최솟값 갱신
        if min_ > num:
            min_ = num
        # 최댓값 갱신
        if max_ < num:
            max_ = num

    else:
        for i in range(10):
            # stack 비어있으면 바로 추가
            if not stack:
                stack.append(i)
                back_tracking()
                stack.pop()
                
            # stack 비어있지 않으면
            elif i not in stack:
                if inequalities[len(stack)-1] == '<' and stack[-1] < i:
                # stack[-1]보다 큰 값만 추가
                    stack.append(i)
                    back_tracking()
                    stack.pop()
                elif inequalities[len(stack)-1] == '>' and stack[-1] > i:
                # stack[-1]보다 작은 값만 추가
                    stack.append(i)
                    back_tracking()
                    stack.pop()
                
import sys
input = sys.stdin.readline

k = int(input())
inequalities = list(input().rstrip().split())
global min_
global max_
min_ = 9876543211
max_ = 0
stack = []
back_tracking()

answer = ''
for i in range(k+1 - len(str(max_))):
    answer += '0'
answer += str(max_) + '\n'
for i in range(k+1 - len(str(min_))):
    answer += '0'
answer += str(min_)
print(answer)

메모리: 30860 KB
시간: 248 ms

링크와 스타트

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이다. 이제 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입출력

Algorithm

back tracking - 재귀
1. start에 숫자 추가
1.1. start가 비어있으면 그냥 추가
1.2. start가 비어있지 않으면 stack에 들어있지 않고 stack의 마지막 숫자보다 큰 숫자만 추가
2. append될 때마다 두 팀의 능력치 차이에 따라 answer 갱신
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. start의 길이가 N-1이 되면 append하기 전에 pop부터 하도록 구현

Code

import sys
input = sys.stdin.readline

def back_tracking(s_start, s_link):
    global answer
    
    # start 길이가 N - 1이 되면 append하기 전에 pop부터 하도록 구현
    if len(start) == N-1:
        pass
    else:
        for num in range(N):
            # start 비어 있으면 숫자 추가
            if not start:
                # start의 첫 번째 원소가 1이면 return
                if num == 1:
                    return answer
                start.append(num)

                # start에 값이 추가될 때마다 능력치 확인
                for i in start[:-1]:
                    s_start += (S[i][num] + S[num][i])
                for i in range(N):
                    if i not in start:
                        s_link -= (S[num][i] + S[i][num])

                # answer값 갱신
                if answer < max(s_start - s_link, s_link - s_start):
                    answer = max(s_start - s_link, s_link - s_start)

                # 재귀함수 호출하고 return되면 pop
                back_tracking(s_start, s_link)
                
                for i in start[:-1]:
                    s_start -= S[i][start[-1]] + S[start[-1]][i]
                for i in range(N):
                    if i not in start:
                        s_link += (S[num][i] + S[i][num])
                    
                start.pop()
            
            # start 비어있지 않으면 start에 들어있지 않고 start의 마지막 숫자보다 큰 값만 추가
            elif num not in start and start[-1] < num:
                start.append(num)

                for i in start[:-1]:
                    s_start += S[i][num] + S[num][i]
                for i in range(N):
                    if i not in start:
                        s_link -= (S[num][i] + S[i][num])

                # answer값 갱신
                if answer > max(s_start - s_link, s_link - s_start):
                    answer = max(s_start - s_link, s_link - s_start)

                # 재귀함수 호출하고 return되면 pop
                back_tracking(s_start, s_link)

                for i in start[:-1]:
                    s_start -= S[i][num] + S[num][i]
                for i in range(N):
                    if i not in start:
                        s_link += (S[num][i] + S[i][num])
                start.pop()
                
N = int(input())
S = []
temp = []
s_link = 0
for _ in range(N):
    temp = list(map(int, input().split()))
    S.append(temp)
    s_link += sum(temp)

start = []
global answer
answer = 100*N*N
s_start = 0
print(back_tracking(s_start, s_link))

메모리: 30864 KB
시간: 7128 ms