[문제실습] Ch 3. 그리디(greedy)

해당 문제와 모범답안은 아래 포스트를 확인해주세요
masso.tistory.com/61?category=891816

[4일차] 이.코.테.다! Ch3 그리디 greedy

문제 및 code

problem1. 거스름돈

def problem1(): # 거스름돈
  # 입력: 1260, 답:6 -> 500*2 + 100*2 + 50*1 + 10*1 
  coins = [500, 100, 50, 10]
  n = int(input("problem1: "))
  cnt = 0

  for coin in coins:
    cnt += n // coin
    n -= coin * (n // coin) # n %= coin

  print(cnt) 

모범 답안과의 비교>
- 파이썬에서 //: 몫을 반환하는 연산자. %: 나머지를 반환하는 연산자임을 상기시키자

- n을 남은 금액으로 갱신할 때 coin 개수와 coin 가격을 곱해 빼는 방법을 사용했는데, 나머지 연산자를 사용해

n %= coin으로 작성했다면 더 간결하고 빠른 코드였을 것이다.

 

problem2. 큰 수의 법칙

def problem2(): # 큰 수의 법칙
  # 5 8 3
  # 2 4 5 4 6
  # 답: 46 -> 6*3 + 5*1 + 6*3 + 5*1 
  # 5 8 5
  # 2 4 5 4 6
  # 답:47 -> 6*5 + 5*1 + 6*2
  n, m, k = map(int,input("problem2: ").split())
  arr = list(map(int,input().split()))

  arr.sort(reverse=True)
  sum = 0
  while m > 0:
    if m > k:
      sum += arr[0]*k
      m -= k
    else:
      sum += arr[0]*m
      m = 0

    if m >= 1:
      sum += arr[1]
      m -=1

  print(sum)

모범 답안과의 비교>

- list를 어떻게 정렬하냐에 따라 다를 수 있는데, 모범 답안에서는 오름차순으로 정렬하여 [n-1],[n-2] 값으로 제일 큰 값과 그 다음으로 큰 값을 구하였다.

- 반복되는 수열의 길이는 (K+1)이고 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.
  여기에 (K+1)*M은 first가 반복하는 횟수가 되고, M이 (K+1)로 나누어 떨어지지 않는 것을 고려했을 때,
  '가장 큰 수가 더해지는 횟수는 int(M/(K+1)) * K + M%(K+1)'

  따라서, 더한 값의 결과는 first * 구한 횟수 + second * (m - 구한 횟수)가 된다.

 

problem3. 숫자 카드 게임

  # 3 3
  # 3 1 2
  # 4 1 4
  # 2 2 2
  # 답: 2
  # 2 4
  # 7 3 1 8
  # 3 3 3 4
  # 답: 3
  n, m = map(int, input("problem3: ").split())
  cards = [list(map(int, input().split())) for _ in range(n)]
  # [[3, 1, 2], [4, 1, 4], [2, 2, 2]]
  # [[7, 3, 1, 8], [3, 3, 3, 4]]

  for i in range(n):
    cards[i].sort()
  cards.sort(reverse=True)
  print(cards[0][0])

 

모범 답안과의 비교>

- 행을 입력받을 때마다 해당 행의 min값을 찾고, 찾은 min값을 이전 min값과 비교하면서 더 큰 min값으로 result 변수를 갱신하는데 나는 그냥 sort를 박아버렸다지...?!

 

problem4. 1이 될 때까지

def problem4():  # 1이 될 때까지
  # 25 5
  # 답:5
  n, k = map(int, input("problem4: ").split())
  count = n % k + n // k
  print(count)

 

모범 답안과의 비교>

- n을 k로 나누고, 1을 빼고 나서 또 다시 k로 나눌 수 있는 경우가 생길 수 있는데, 빨리 풀고 싶은 마음에 그 경우를 고려하지 못해서 정말 간단한 코드가 나왔다...!- k로 나눌 수 있는 만큼 나누고
  1) n<k 라면 그만큼 1을 빼면 되기 때문에 break를 한다.   2) n>=k 라면 한 번 k를 더 나누고 이에 맞게 갱신하고 반복한다!

 

main 함수

def __main__():
  problem1()
  problem2()
  problem3()
  problem4()

__main__()