난이도
Silver 2
풀이 참고 유무
?
막힌 부분
시간 초과
문제
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
예제 입력
8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0
예제 출력
1
문제 검토
팀을 결정하는 것에 있어서 백트랙킹 과정이 필요한 문제이다.
풀이(python)
Python
from sys import stdin
input=stdin.readline
start=set()
n=int(input())
matrix=[list(map(int,input().split())) for _ in range(n)]
person=[True]*n
def abil():
starttmp=0
linktmp=0
for x in range(n):
for y in range(x,n):
if x in start and y in start:
starttmp+=matrix[x][y]+matrix[y][x]
elif x not in start and y not in start:
linktmp+=matrix[x][y]+matrix[y][x]
return abs(starttmp-linktmp)
answer=10000000
def dfs(depth):
global answer
if depth==int(n/2):
answer=min(answer,abil())
return
for x in range(n):
if person[x]:
start.add(x)
person[x]=False
dfs(depth+1)
start.remove(x)
person[x]=True
dfs(0)
print(answer) 아이디어
#N=6이라면
#0번부터 시작해서 팀 리스트에 넣는다.
#depth가 n/2이라면 한 팀을 결성한 것이므로 자동적으로 나머지 팀이 결정된다.
#그 뒤 팀 능력치를 계산한 뒤 차를 구해 리턴한다.
#돌아오면서 리스트에서 삭제해준다.
시간복잡도
#백트랙킹이라 잘 가늠이 되지는 않는다.
#N이 4-20R까이지고 짝수만 들어오기 때문에 4,6,8,10,12,14,16,18,20 총 9가지이다.abs
#O(n!)를 생각하면 가능해보인다.
자료구조
#1차원 리스트:스타트팀 링크팀, 2차원 행렬 리스트:각 선수들의 케미
처음엔 위 전략으로 문제를 풀지 않고 start와 link팀을 각각 따로 구성했고 테스트 케이스까지 성공적으로 나왔지만, 시간초과가 나왔다.
팀을 따로 구성하는 과정에서 abil함수가 너무 많은 시간을 차지하나 싶어서
위 아이디어를 따라서 코드를 아래처럼 바꾸어 보았다.
from sys import stdin
input=stdin.readline
n=int(input())
matrix=[list(map(int,input().split())) for _ in range(n)]
person=[True]*n
def abil():
starttmp=0
linktmp=0
for x in range(n):
for y in range(x,n):
if not person[x] and not person[y]:
starttmp+=matrix[x][y]+matrix[y][x]
elif person[x] and person[y]:
linktmp+=matrix[x][y]+matrix[y][x]
return abs(starttmp-linktmp)
answer=10000000
def dfs(depth):
global answer
if depth==int(n/2):
answer=min(answer,abil())
return
for x in range(n):
if person[x]:
person[x]=False
dfs(depth+1)
person[x]=True
dfs(0)
print(answer) 역시 시간초과가 나왔다.
힌트를 살짝 얻으니 person의 True,False만으로도 팀을 구성할 수 있음을 알았다.
굳이 팀에 대한 자료구조를 사용하지 않아도 됐다.
그래도 내 원래 풀이와 시간복잡도는 비슷할 것이라고 생각했는데 역시나 아래 코드도 시간초과가 나왔다.
from sys import stdin
input=stdin.readline
n=int(input())
matrix=[list(map(int,input().split())) for _ in range(n)]
person=[True]*n
answer=10000000
def dfs(depth,idx):
global answer
if depth==int(n/2):
starttmp=0
linktmp=0
for x in range(n):
for y in range(n):
if not person[x] and not person[y]:
starttmp+=matrix[x][y]
elif person[x] and person[y]:
linktmp+=matrix[x][y]
answer=min(answer,abs(starttmp-linktmp))
return
for x in range(idx,n):
if person[x]:
person[x]=False
dfs(depth+1,idx+1)
person[x]=True
dfs(0,0)
print(answer) 그래서 풀이를 봤는데 나랑 변수명 빼고 다른 로직이 없었다.
idx 역시 나는 원래 사용하지 않다가 풀이를 보고 사용했는데 그래도 시간초과가 났다.
후에는 아예 변수명 빼고 모든 걸 똑같이 만들었다.
앞에 초기화하는 과정까지도 똑같이 했지만, 시간초과가 났다.
변수명 때문에 시간초과가 생길 수는 없다고 생각하는데 검색해보니 백준에서 가끔 이런 일이 있는 것 같기도 하다.
걸린 시간
39:23 - 첫 풀이 기준(테케O)
총평
아이디어를 구상하고 구현하는 것이 어렵지 않은 백트랙킹이지만, 뭔가 중요하지 않은 부분의 시간초과를 해결하려고 시간을 많이 사용한 것 같아서 아쉬운 문제이다.
