[이것이 코딩테스트다] Chapter 02. 그리디

 

실전문제 3. 숫자 카드 게임

 

숫자 카드 중에서 가장 높은숫자가 쓰인 카드 한 장을 뽑는 게임.

 

but. 게임 룰

1. 먼저 뽑고자 하는 카드가 포함되어 있는 행 선택

2.  각 행 중에 가장 작은 수만을 뽑을 수 있음

 

Sol

행별로, 가장 작은 숫자를 알아냄

작은 숫자들 중에 가장 큰 수를 뽑아내면 됨

 

소스코드

n = 3 # 행의 크기
m = 3 # 열의 크기
A = [[3,1,2],[4,1,4],[2,2,2]] # 리스트 A 

result = 0


# 한 줄씩 확인
for i in range(n):
    data = A[i]
    # 현재 줄에서 가장 작은 수 찾기
    min_value = min(data)
    # 가장 작은 수 들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

 

 

 

실전 문제 4. 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

N과 K가 주어질 때 1번 혹은 2번 과정을 수행해야 하는 최소 횟수를 구하시오

 

Sol.

1. N이 K의 배수가 될 때까지 1씩 빼기

2. N을 K로 나누기

 

단순하게 푸는 답안

n = 25
k = 3

result = 0

#n이 K 이상이라면 K로 계속 나누기

while n >= k:
    while n%k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)