교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 3 그리디
실전문제 3-2 큰 수의 법칙 92p
큰 수의 법칙
문제
여기서 큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음
입력
첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며 각 자연수는 공백으로 구분
둘째줄에 N개의 자연수가 주어짐. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1이상 10000이하의 수로 주어짐
입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력
첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력
입력 예시
5 8 3
2 4 5 4 6
출력 예시
46
풀이
접근 1
- 줄에서 가장 작은 값만 저장해서 그 아이들 중 최댓값을 찾아주자
Note
- 뭔가 sort 같은 거 좀 안쓰고? 코딩하는 것도 좀 연습해야 할 것 같기는 하다
제출 1 - 정답
n, m = map(int, input().split())
mins = []
for i in range(n):
arr = list(map(int, input().split()))
mins.append(min(arr))
print(max(mins))
오답노트
책보다 메모리를 더 많이 쓴 것 같당 뭔가 내가 습관이 저장해버리고 나중에 처리해버리는 게 있는 것 같긴 하다 이런 것도 수정해나가면 넘 좋을 듯 굳
- 책에 있는 솔루션
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
data = list(map(int, input().split()))
# 현재 줄에서 '가장 작은 수' 찾기
min_value = min(data)
# '가장 작은 수'들 중에서 가장 큰 수 찾기
result = max(result, min_value)
print(result) # 최종 답안 출력결과
- 풀이시간 : 5분
References
이것이 코딩 테스트다 with 파이썬 - 나동빈 저
