이것이 코딩테스트다 with 파이썬 | 그리디 ②

---

그리디 실전문제

3) 숫자카드 게임

여러 숫자 카드들 중에서 가장 높은 숫자 카드 한장을 뽑는 게임

ⓛ 카드가 N*M 형태로 놓여있다 (N:행 M:열)
② 뽑을 카드의 행을 선택한다
③ 선택된 행 중 가장 숫자가 낮은 카드를 뽑는다
=> 1~3번을 고려하여 가장 높은 숫자의 카드를 뽑도록 해야함

(입력) : N, M (첫 번째 줄) , 각 카드에 적힌 숫자 (두 번째 줄)
(출력) : 선택한 카드에 적힌 숫자를 출력

👇 답지를 보기 전 작성한 코드

N,M=map(int,(input().split()))
card=list()
for n in range(0,N):
  row=list(map(int,(input().split())))
  card.append(row)

min_card=list()
for n in range(0,N):
  min_card.append(min(card[n]))
print(max(min_card))

📝각 행마다 가장 작은 수를 찾는다 => 작은 수들 중 가장 큰 수

📌답안 예시를 본 후 피드백
문제 푸는 방식과 흐름은 거의 동일했으나, 내가 쓴 코드같은 경우는 for문을 따로 2개를 쓰기 때문에 코드가 쓸데없이 길어졌음. 하나로 묶어서 구할 수도 있었다.

👇 피드백 후 코드

N,M=map(int,(input().split()))
card=list()
#result=0 책 풀이
for n in range(0,N):
  row=list(map(int,(input().split())))
  card.append(min(row))
  # min_value=min(row) 책 풀이
  #result=max(result,min_value) 책 풀이
print(max(card))

---

4) 1이 될 때까지

N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택이 가능하다


① N에서 1을 뺀다

② N을 K로 나눈다

=> N과 K가 주어질 때, N이 1이 될 때까지 ①번 혹은 ②번의 과정을 수행해야 하는 최소횟수는?


(입력) : N, K (N>=K)

(출력) : ①번 혹은 ②번의 과정을 수행 횟수 최솟값

👇 답지를 보기 전 작성한 코드

def sol_1(N):
  ct=0
  while N!=1:
    N=N-1
    ct+=1
  return ct

def sol_2(N,K):
  ct=0
  while N!=1:
    N=N//K
    ct+=1
  return ct

N,K=map(int,(input().split()))
print(min(sol_1(N),sol_2(N,K)))

📌 답안 예시를 본 후 피드백
ⓛ 나누는게 빼는 것보다 더 빠르게 줄어듦 => 확률상 최소 횟수에 더 가까울 가능성이 높음
② 문제에 대한 이해를 잘못한 점도 있었음. => 하나'만' 선택해서 반복적으로 계산하는 것이 아님
👉 나눠지는 과정을 택해서 계속 반복하여 계산했는데 나중에 나눠지지못해서 0이 되는 경우가 될 수도 있기 때문에

👇 피드백 후 코드

N,K=map(int,(input().split()))
ct=0
while N>=K: 
  if N<K:
    while N%K!=0:
      N-=1
      ct+=1
  else:
    N=N//K
    ct+=1
print(ct)