그리디

백준 문제의 DP에서 심각한 벽을 느껴 화제 전환김에 이전에 사둔 이코테 책을 풀어보려고 한다. 문제에 대한 부분은 따로 적진 않겠다. 

 

숫자 카드 게임

문제의 의도

각 행 별로 가장 작은 값을 구하고 그 중에서 가장 큰 값을 추출하면 된다.

n, m = map(int, input().split())
result = []

for _ in range(n):
    num_list = list(map(int, input().split()))
    result.append(min(num_list))

print(max(result))

내가 푼 방식은 리스트에 각자의 작은 값을 담고 그 리스트에서 가장 큰 값을 추출했다.

 

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

for _ in range(n):
    num_list = list(map(int, input().split()))
    min_num = min(num_list)
    result = max(result, min_num)

print(result)

굳이 리스트를 쓰지 않고 가장 작은 값을 구해 max() 함수를 사용하여 큰 값을 추출하도록 하는 방법도 있다.

 

1이 될 때까지

문제의 의도

입력받는 n이 1이 될 때까지의 가장 최소의 횟수를 구한다.

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

while n > 1:
    if n % k == 0: 
        n = n // k
        cnt += 1
    else: 
        n -= 1
        cnt += 1

print(cnt)

역시나 눈에 보이는 방법으로 먼저 풀어본 방식은 위와 같다. 책에서 다른 풀이를 제시해 머릿속으로 곰곰히 생각해보고 프로세스를 구상해서 코드로 다시 재구성해보았다.

 

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

# 1. n // k한 것에 k를 곱하면 나눈 몫의 배수 중 가장 큰 값이 나옴
# 2. 1번의 경우 n에서 1번을 뺐을 때 1을 빼는 경우의 수가 나옴
# 3. 그것을 result에 담음.
# 4. n이 1이 되었을 때, (n // k) * k는 무조건 0이 되어 n - num은 1로 result에 무조건 1이 더해지는 오류가 발생하기에 1을 빼줌

while True:
    num = (n // k) * k
    print("num >>>>>" + str(num))
    print("n >>>>>" + str(n))
    result += (n - num)
    print("result >>>>>" + str(result))

    if (n < k): break
    n = n // k
    result += 1

print(result - 1)

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

# 1. n // k한 것에 k를 곱하면 나눈 몫의 배수 중 가장 큰 값이 나옴
# 2. 1번의 경우 n에서 1번을 뺐을 때 1을 빼는 경우의 수가 나옴
# 3. 그것을 result에 담음.
# 4. n이 1이 되었을 때, (n // k) * k는 무조건 0이 되어 n - num은 1로 result에 무조건 1이 더해지는 오류가 발생하기에 1을 빼줌

while True:
    num = (n // k) * k
    result += (n - num)

    if (n < k): break
    n = n // k
    result += 1

print(result - 1)

첫번째에서 1을 k의 배수가 될 수 있는만큼 빼주고 그것을 연산 횟수에 추가해준다음 나눌 수 있는 상황인지 확인하고 나눌 수 있으면 n의 값을 k로 나눈 몫으로 대체하고 횟수를 하나 더 증가시켜줬다.

 

근데 결과는 항상 1이 높은 숫자가 나오길래 왜 그런지 생각부터 해봤다. 결과적으로는 n이 1이 되었을 때, 무한루프를 빠져나와줘야하는데 연산을 한 번 더해버리는 상황이 발생해서이다. 그렇기에 그 연산을 한 번 빼주어야 비로소 올바른 답이 도출되는 걸 알았다.