Python3
문제
키워드
- 백트래킹
문제 풀이
문제 요구사항
n개의 일이 주어질 때 이를 아침과 저녁으로 n/2개씩 나누어 처리한다.
일마다 특성이 다르기 때문에 같이할 때의 업무 강도를 나타내는 업무 간의 상성 Pij가 존재한다.
아침과 저녁의 일의 힘든 정도가 너무 차이가 나면 일하기가 싫어지기 때문에, 아침의 하는 일의 업무 강도와 저녁에 하는 일의 업무 강도의 차이의 최솟값을 구하고자 한다.
아침과 저녁의 업무 강도의 차이의 최솟값을 구하는 프로그램.
변수 및 함수 설명
- n: 일의 양
4 ≤ n ≤ 20.
n은 2의 배수이다. - P: 업무 간의 상성
- tmp : 아침 업무 강도
- tmp2 : 저녁 업무 강도
- ans : 업무 강도 차이의 최솟값을 저장하는 변수
- res: 업무 강도를 저장하는 변수
- intensity(c) : 업무 강도 구하는 함수
- dfs(idx, depth) : 업무 강도 차이의 최솟값 구하는 함수
풀이
(입력 및 선언)
- 일의 양 n 입력 받기
- p 배열에 업무 상성 저장하기
- tmp의 첫 번째 값은 0이다.
=> Pij = 0 (i=j)라는 조건에 의해 - ans는 최솟값으로 초기화한다.
(강도 구하기)
- res 변수를 0으로 초기화한다.
- 아침 저녁 각각 n/2의 일을 처리하므로 n//2만큼 반복한다.
- 인덱스를 다음으로 옮기고 반복문을 돈다.
- res에 Pij, Pji 값을 더해 저장한다.
- 반복문이 종료되면 res를 반환한다.
(최솟값 구하기)
- 만약 계속 깊이 들어가며 탐색하다가 n//2 값이 되면 아침 저녁 일의 강도 차이를 ans에 넣는다.
- 재귀를 돌기 위해 idx를 하나 증가시키고, n까지 반복한다.
- 배열을 추가하고 깊이를 1 증가시킨 후 재귀를 돈다.
- return으로 돌아오면 tmp.pop()이 실행되고 배열을 이전 상태로 만들어 준다.
(함수 실행 및 최종 값 출력)
- dfs 함수에 idx는 0, depth는 1을 인자로 호출한다.
- ans 값을 최종 출력한다.
최종 코드
n = int(input())
# 상성 리스트 저장
p = []
for _ in range(n):
p.append(list(map(int, input().split())))
# 강도 구하기
def intensity(c):
res = 0
for i in range(n//2):
for j in range(i+1, n//2):
res += p[c[i]][c[j]]
res += p[c[j]][c[i]]
return res
# 최솟값 구하기
def dfs(idx, depth):
global ans
if depth == n//2:
tmp2 = [i for i in range(n) if i not in tmp]
ans = min(ans, abs(intensity(tmp) - intensity(tmp2)))
for i in range(idx+1, n):
tmp.append(i)
dfs(i, depth+1)
tmp.pop()
tmp = [0]
ans = float("INF")
dfs(0, 1)
print(ans)피드백
재귀함수
def 재귀함수(n):
if 정답이면 :
출력 or 저장
else : 정답이 아니면 :
for 모든 자식 노드에 대해서:
if 정답에 유망하다면(답의 가능성이 있으면) :
자식노드로이동
재귀함수(n+1)
부모노드로 이동백트래킹
def 백트래킹(n):
if 정답이면 :
출력 or 저장
else :
for 모든 자식 노드에 대해 :
if 유망한지확인(m) :
자식노드로 이동
백트래킹(n+1)
부모노드로 이동
def 유망한지확인(m):
if 조건에 안맞으면 :
return False
return True참고 : https://edder773.tistory.com/75
백트래킹 문제 풀어보기
N-Queen 백준
I mean