9007번: 카누 선수
문제 )
국제 카누 경주 챔피언십 (International Canoe Sprint Championship : ICSC)가 머지 않아 개막된다. ICSC에서 인증하는 공식 보트는 C1, C2 그리고 C4로 구성되며, "C"는 카누를 그리고 숫자는 노를 젓는 사람의 수를 의미한다. 카누 경주는 잔잔한 물 위의 여러개로 구획된 직선 코스에서 이루어진다. ICSC에서는 국제 경기를 200m, 500m 그리고 1000m로 구분하고 있다.
한국 스포츠 학교(Korea Sports School : KSS)는 ICSC 의 C4 1000m 경기에 참가할 예정이다. KSS에는 같은 수의 학생으로 구성된 4개의 반을 가지며, 각 반에서 1명씩을 선출하여 경기에 참가한다. KSS에는 다수의 C4 보트를 가지고 있으며 각 보트는 선수들의 몸무게 합이 특정 값에 근사할 때 최대의 성과를 낼 수 있다. 예를 들어 특정 값이 300이고 각 반의 학생들의 몸무게가 아래와 같다고 하자.
- Class-1: 60, 52, 80, 40
- Class-2: 75, 68, 88, 63
- Class-3: 48, 93, 48, 54
- Class-4: 56, 73, 49, 75
각 반에서 차례로 60,75,93 그리고 73 학생을 선택하게 되면 몸무게 합이 301으로 300에 가장 근사하게 된다. 몇몇의 경우에는 두개의 근사값이 나올 수 있다. 예를 들어 특정 값이 200일 때, 몸무게의 합이 198과 202가 나올 수 있으며 이러한 경우에는 더 작은 값이 카누 게임 진행에 더 적합하다. 따라서 몸무게의 합이 198인 학생들이 선택받게 된다.
보트의 특정값과 학생들의 몸무게가 주어졌을때, 위의 조건을 만족하는 4명의 학생을 선택하시오.
입력 :
이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그리고 n( 1 ≤ n ≤ 1,000 )은 KSS 각 반의 학생수이다.
이어지는 4개의 줄에 차례로 각 반의 학생들의 몸무게가 n개씩 주어진다. 이때 몸무게는 1에서 10,000,000까지이다.
출력 :
출력은 표준 출력을 이용한다. 각 테스트 케이스에 해당하는 값을 한 줄에 출력한다. 해당 줄에는 카누 선수로 지목된 학생들의 몸무게의 총합이 포함되어 있어야 한다.
풀이)
|
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
# 9007. 카누선수
T = int(input())
for _ in range(T):
k, n = map(int, input().split())
li = [list(map(int, input().split())) for i in range(4)]
as1 = []
as2 = []
# 4개 클래스의 선수들을 2개의 클래스로 압축하는 과정
for i in range(n):
for j in range(n):
as1.append(li[0][i] + li[1][j])
as2.append(li[2][i] + li[3][j])
as1.sort() # 오름차순 정렬
as2.sort(reverse = True) # 내림차순 정렬
s = 0
e = 0
ans = as1[s] + as2[e]
# 둘 중 하나라도 리스트를 벗어난다면 반복문이 종료됨.
while s < len(as1) and e < len(as2):
# 기존의 차보다 옮긴 후의 차가 더 작다면 정답 갱신
if abs(as1[s] + as2[e] - k) < abs(ans - k):
ans = as1[s] + as2[e]
# 이 코드가 들어간 이유는 차가 같더라도, 몸무게가 더 작은
# 경우가 답이 되기 때문에
elif abs(as1[s] + as2[e] - k) == abs(ans - k):
if ans > as1[s] + as2[e]:
ans = as1[s] + as2[e]
# 원하는 몸무게보다 작다면
if as1[s] + as2[e] < k:
s += 1
# 원하는 몸무게보다 크다면
elif as1[s] + as2[e] > k:
e += 1
else: # 원하는 몸무게 조합이 있는 경우
break
# 조합의 차가 0이 될 경우에 while문의 조건을 만족해도 나오므로 체크
if s < len(as1) and e < len(as2):
if abs((as1[s] + as2[e] - k)) < (ans - k):
ans = as1[s] + as1[e]
print(ans)
|
cs |
같은 차를 가진 조건에서 몸무게가 더 낮은 선수를 찾는 조건을 짜는 게
코드를 짤 당시에는 생각하는 게 참 어려웠다.
그래서 그 부분은 다른 블로그의 도움을 좀 받았는데
어려워한 부분 말고는 코드가 거의 똑같아서 참 신기했다.출처 : https://www.acmicpc.net/problem/9007
9007번: 카누 선수
이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그
www.acmicpc.net
'Develop > 백준 (python)' 카테고리의 다른 글
| [백준] 1427번: 소트인사이드 (python) (0) | 2022.02.19 |
|---|---|
| [백준] 2750번: 수 정렬하기 (python) (0) | 2022.02.19 |
| [백준] 14465번: 소가 길을 건너간 이유 5 (python) (0) | 2022.02.18 |
| [백준] 3273번: 두 수의 합 (python) (0) | 2022.02.18 |
| [백준] 1644번: 소수의 연속합 (python) (0) | 2022.02.18 |
