Algorithm ) Greedy (2)

실전 문제 풀이 

2️⃣ 문제 2 : 숫자 카드 게임

- 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 

- 게임 룰은 다음과 같다.

- 1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 

- 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다 

- 3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다 

- 4. 따라서 처음에 카드를 골라낼 행을 선택 할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 

🥦 문제 해결 아이디어 : 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것 

 

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)

 

 

3️⃣ 문제 3 : 1이 될때까지 

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

단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 

- N에서 1을 뺀다. 

- N을 K로 나눈다.

 

예를들어, N이 17이고 K가 4라고 가정하자. 이때 1번의 과정을 1번 수행하면 N은 16이 된다. 

이후에 2번의 과정을 2번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 

이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 떄까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하기

 

🥦 문제 해결 아이디어 : 최대한 많이 나누기 

- 어떠한 수가 있을 때 , 2이상의 수로 나누는 것이 1을 빼는 것보다 숫자를 훨씬 많이 줄일 수 있음 

 

n,k = map(int, input().split())
result = 0

# N이 K이상이라면 K 로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는 다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

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

print(result)

# 더 효율적인 풀이법
n,k = map(int, input().split())
result = 0

while True:
    # N 이 K로 나누어 떨어지는 수가 될 떄까지 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 k보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)

- 2번째 풀이법 while문 설명 추가 ! 

- target 값에 (n // k) * k 라는 값을 넣으면 n이 k로 나누어 떨어지지 않더라도 가장 가까운 k로 나누어 떨어지는 수가 저장됨 

- n에서 1을 빼는 과정을 몇 번 반복할 것인지 계산해서 result에 저장

- 이제 n은 target이 되는 것 -> n 이 k보다 작다면 반복문 탈출

- 이후에 k로 나누기 !