그리디 알고리즘 2,3: 큰 수의 법칙, 숫자 카드 게임

화승이·2023년 3월 23일
0
  • 오늘 해설 해 볼 문제들은 나동빈 저자의 <이것이 코딩테스트다 with 파이썬> 책을 참고하여 해설을 해 본 문제들이다. 관련 알고리즘은 문제 사이트 ( 백준, 코드업 등..) 에서 찾아서 조만간에 연습으로 해볼 생각이다.

1. 큰 수의 법칙

  1. 문제 소개

    • 입력조건: 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
    • 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
    • 입력으로 주어진 K는 항상 M보다 작거나 같다.
  2. 입력 예시, 출력 예시

    5 8 3
    2 4 5 4 6 -> 46

  1. 정답
  • 첫번째 코드 : 단순하게 리스트에서 가장 큰 수와 두 번째로 큰 수를 가져와서 주어진 만큼 계산함으로써 정답을 구한다.

n , m , k = map(int,input().split())
data = list(map(int,input().split()))

data.sort()
first = data[n - 1]
second = data[n - 2]

result = 0

while True:
for i in range(k):
if m == 0:
break
result += first
m -= 1

if m == 0:    
    break
result += second    
m -= 1      

print(result)


  • 반복되는 수열을 계산하여 해결한다.

    가장 큰 수를 K번 만큼 더하고, 두 번 째로 큰 수를 한 번 더하는 것을 반복하는 것은 일정하게 더해지는 수열 형태를 띄는 것을 확인 할 수 있다. 바로, M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수로 작용해 계산을 하게 된다. 위 식을 수열의 식과 나타내면 다음과 같다.

    int(M / (K + 1)) * K + M % ( K + 1)


n , m , k = map(int,input().split())
data = list(map(int,input().split()))

data.sort()
first = data[n - 1]
second = data[n - 2]

count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) first
result += (m - count)
second
print(result)


2. 숫자 카드 게임

  1. 문제 소개

    • 첫쨰 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 <= N, M <= 100)
    • 둘쨰 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
  2. 입력 예시, 출력 예시

    3 3
    3 1 2
    4 1 4
    2 2 2 - > 2

  3. 정답
    답은 간단하다. 문제에서 주어진 리스트들 중에서 가장 작은 값을 추출한 다음에 그 수 중에서 가장 큰 수를 찾으면 되는 것이다. 이 풀이도 두 가지의 해결방안이 있다.

  • min() 함수를 이용하는 답안

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)


  • 2중 반복문 구조를 이용하는 답안

n , m = map(int, input().split())

result = 0

for i in range(n):
data = list(map(int, input().split()))
min_value = 10001
for a in data:
min_value = min(min_value, a)
result = max(result, min_value)

print(result)


  • 다음으로 이 책에서 다루는 그리디 유형의 알고리즘은 끝나지만, 앞으로 더 찾아서 해결해보도록 하겠다.
profile
이제부터 하고싶은것만 하면서 살거야

0개의 댓글