스타트와 링크
https://www.acmicpc.net/problem/14889
14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
문제를 해결하기 위해 단계를 나눠보았다.
1. N명을 두 팀으로 나눈다.
2. 두 팀의 능력치를 구한다.
3. 능력치의 차를 구한다.
각각 함수로 만들었다.
1. N명을 두 팀으로 나눈다.
이전에 푼 문제를 변형했다. 15650번 문제는 1부터 N까지의 자연수 중 M개를 중복없이, 오름차순 수열을 구하는 문제였다. 이 문제는 1부터 N까지의 자연수 중 N/2개를 중복없이 고르는 것과 같다.
(참고: https://joylee-developer.tistory.com/102)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import sys
# 입력
N = int(sys.stdin.readline())
S = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
team = []
member = []
#팀을 구성함
def make_team(num):
# 멤버가 N/2명이면 팀의 능력치를 구해 저장한다
if len(member) == N/2:
ability = get_ability()
team.append(ability)
return
# 멤버를 한명씩 추가한다
# 중복없고, 오름차순 위해 입력받은 수+1 부터 시작한다
for i in range(num+1, N+1):
member.append(i)
make_team(i)
member.pop()
|
cs |
15650번과 다른점은 15650번은 수열을 구한 후 바로 화면에 출력했지만 이번 문제에서는 구한 수열로 팀의 능력치를 구한다.
2. 두 팀의 능력치를 구한다.
능력치는 Sij와 Sji가 다르기 때문에 둘 다 구해서 더해줘야 한다.
멤버는 1부터 N까지의 수 중에 골랐기 때문에 S에 인덱스로 넣을땐 -1을 해줘야 한다.
|
1
2
3
4
5
6
7
8
9
10
|
# member는 중복없이 고른 N/2명의 팀
# S 는 입력받은 능력치이다
# 예제입력1의 S = [[0, 1, 2, 3], [4, 0, 5, 6], [7, 1, 0, 2], [3, 4, 5, 0]]
def get_ability():
ability = 0
for i in member:
for j in member:
ability += S[i-1][j-1]
return ability
|
cs |
i=j인 경우는 어차피 0이기 때문에 더해도 영향이 없다. 그래서 굳이 두 쌍을 구해서 S[i][j], S[j][i]를 따로 구하지 않고
중복을 포함해 member에서 두 수를 구하도록 동일한 for문을 두 번 실행했다.
모두 더한 ability를 반환해 make_team() 안에서 team이라는 list에 저장하도록 했다.
3. 능력치의 차를 구한다.
팀을 구할 때 오름차순으로 차례대로 저장했는데 구성을 확인하면 다음과 같다.
4명중에 두 명을 중복없이 오름차순으로 고르면 여섯개의 수열이 나온다.
그런데 문제를 해결하기 위해서는 나눠진 팀을 짝지어야 한다.
위의 경우에는 team[0]과 team[5] / team[1]과 team[4] / team[2]와 team[3]을 짝지어서 능력치의 차를 구해야 한다.
이것을 for문으로 표현하면 아래와 같다.
|
1
2
3
4
5
6
7
|
def check_gap():
gap = [] # 차이를 저장한 list
for i in range(int(len(team)/2)):
# 나눠진 두 팀의 능력치의 차이를 절대값으로 구해 gap에 저장한다
gap.append(abs(team[i] - team[-i-1]))
# 차이의 최소값을 반환한다
return min(gap)
|
cs |
첫번째와 마지막, 두번째와 뒤에서 두번째를 짝지어야 하므로
i의 범위는 0에서 len(team)/2까지 하고,
team[i] - team[-i-1] 으로 (i번째 팀의 능력치) - (뒤에서 i번째 팀의 능력치)의 절대값을 구한다.
list의 index의 경우 맨 첫번째가 [0]이고, 맨 마지막이 [-1]이므로 뒤에서 i번째는 [-i-1]로 입력해야 한다.
위의 함수들로 구성한 전체 코드이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import sys
N = int(sys.stdin.readline())
S = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
team = []
member = []
# 능력치를 구한다
def get_ability():
ability = 0
for i in member:
for j in member:
ability += S[i-1][j-1]
return ability
# 팀을 구성한다
def make_team(num):
if len(member) == N/2:
ability = get_ability()
team.append(ability)
return
for i in range(num+1, N+1):
member.append(i)
make_team(i)
member.pop()
# 능력치의 차이를 구한다
def check_gap():
gap = []
for i in range(int(len(team)/2)):
gap.append(abs(team[i] - team[-i-1]))
return min(gap)
make_team(0)
print(check_gap())
|
cs |
사실 파이썬으로 작성하면 또 시간초과가 나올 줄 알았는데 다행히 나오지 않았다.
문제 해결의 단계를 나눠서 따로 함수로 코드를 작성하니 생각보다 어렵지 않게 해결할 수 있었다.
* list의 복사
코드를 작성하면서 초반에 팀 구성을 확인하기 위해 team.append(member)를 했는데 이상한 결과가 나왔다.
함수 밖에서 print(team)을 하면 아예 결과가 [[], [], [], [], [], []]으로 출력되고, append함수를 실행할 때 마다 team을 확인해봤더니 다음과 같았다.
[[1, 2], [1, 3]...] 이런 식도 아니고 마지막 member를 넣을 땐 [3, 4]가 6개가 들어있고, 함수에서 코드가 모두 진행되고 나면 []으로 변하는 것이었다.
곰곰이 생각해보니, member가 바뀔 때마다 team안에 있는 리스트의 값도 바뀌는 것이었다.
나는 append(member)를 하면 member의 내용이 복사되어 team안에 저장된다고 생각했는데 그것이 아니라 같은 메모리를 참조하는 리스트가 저장되는 것이었다. id()로 메모리 주소를 확인하면 같은 주소임을 알 수 있다.
그래서 team안에 6개의 리스트가 입력되긴 했는데, 함수가 종료되고 나면 member안에 저장된 수들이 모두 pop()으로 제거되기 때문에 빈 리스트만 남는 것이었다.
그래서 멤버를 확인하기 위해 슬라이싱을 위해 복제본을 team 안에 넣어주었다.
team.append(member[:])로 저장할 수 있다.
이렇게 저장해주면 member의 복제본을 team에 저장할 수 있다.
|
1
2
3
4
5
6
|
def make_team(num):
if len(member) == N/2:
# team.append(member) 은 복사본을 저장하지 않는다
team.append(member[:])
print(team)
return
|
cs |
id로 확인해보면 주소가 다른 것을 확인할 수 있다.
member라는 list를 복사하는 다른 방법으로는 아래와 같다.
member[:]
list(member)
member.copy()
[] + member
참고한 사이트
https://joylee-developer.tistory.com/102
(파이썬) 백준 알고리즘 - 15650번
N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해.
joylee-developer.tistory.com
파이썬 리스트 복사하기
오늘은 상당히 기초적이면서도 쉽게 실수 할 수 있는 부분을 다뤄보고자 한다. 바로 나를 포함한 초보자들이 실수할 수 있는 파이썬 리스트를 다른 리스트에 복사하는 방법에 대해 소개한다.
inkkim.github.io
'알고리즘' 카테고리의 다른 글
| (파이썬) 백준 알고리즘 - 14888번 / permutation() (0) | 2021.09.08 |
|---|---|
| (파이썬) 백준 알고리즘 - 9663번 (0) | 2021.09.01 |
| (파이썬) 백준 알고리즘 - 15652번 (0) | 2021.08.31 |
| (파이썬) 백준 알고리즘 - 15651번 (0) | 2021.08.31 |
| (파이썬) 백준 알고리즘 - 18870번 (0) | 2021.08.31 |