7568번: 덩치
우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩
www.acmicpc.net
문제 해결을 위한 과정
문제를 잘 살펴보면 자신보다 몸무게 그리고 키 모두 큰 사람의 수 + 1이 자신의 덩치 등수가 되는 것을 알 수 있습니다.
따라서 입력받은 몸무계와 키를 각각의 사람마다 묶어서 리스트에 저장해준 후 자신보다 몸무게 그리고 키가 모두 큰 사람의 수를 세는 것으로 쉽게 해결할 수 있습니다.
문제 해결을 위한 팁
문제의 조건에서 데이터의 개수인 N이 50이하인것을 확인할 수 있습니다. 따라서 O(N^2)의 시간 복잡도를 가진 알고리즘을 적용해도 해결할 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
n = int(input())
data = [] # 입력받은 정보를 저장할 리스트 data
ans = [] # 등수정보를 저장할 리스트 ans
for i in range(n):
a, b = map(int, input().split())
data.append((a, b)) # 몸무계와 키를 묶어서 append 해줌
for i in range(n):
count = 0
for j in range(n):
if data[i][0] < data[j][0] and data[i][1] < data[j][1]: # 몸무게와 키 모두 자신보다 큰 사람의 수를 센다
count += 1
ans.append(count + 1) # 덩치 등수는 자신보다 몸무계 키 모두 큰 사람의 수 + 1 이므로 count + 1을 ans에 append한다.
for d in ans:
print(d,end=" ")
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 10773: 제로(Python) (0) | 2021.02.03 |
|---|---|
| 백준 알고리즘 1475: 방 번호(Python) (0) | 2021.02.03 |
| 백준 알고리즘 1966: 프린터 큐(Python) (0) | 2021.02.02 |
| 백준 알고리즘 1316: 그룹 단어 체커(Python) (0) | 2021.02.02 |
| 백준 알고리즘 1152: 단어의 개수(Python) (0) | 2021.02.02 |