코딩 공부 - 그리디 알고리즘 문제 풀이 (2)

3) 숫자 카드 게임

 

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

입력

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1<=N,M<=100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

(1) 내 풀이

arr1 = list(map(int, input().split()))
# 두 번째 줄 읽기

card_arr = []
for _ in range(arr1[0]):
    arr2 = list(map(int, input().split()))[:arr1[1]]
    card_arr.append(arr2)

min_arr = []
for arr in card_arr:
    min_arr.append(min(arr))

print(max(min_arr))

 

(2) 정답 풀이

# min()함수를 이용하는 답안 예시
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중 반복문 구조를 이용하는 답안 예시
 
 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)

 

내 풀이와 예시 답안을 비교해보자면, 1번 예시와 유사한 답안이란걸 알 수 있지만 그러나 굳이 2번의 반복문을 쓰면서 시간 복잡도만 올린 모습을 볼 수 있다. 앞으로는 조금 더 간단하게 코드를 짜는 연습을 해야할 것 같다. 

 

4) 1이 될 때까지 

 

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

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

---

[입력 조건]

• 첫째 줄에 N(2≤ N ≤ 100,000)과 K(2≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다. 

 

[출력 조건]

• 첫째 줄에 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

(1) 내 풀이

 

이 문제를 처음 봤을 때 나누기를 우선하고 안된다면 빼기를 하면 된다는 생각이 들었다.  

 

1. N이 M의 배수가 아니라면 배수가 될 때까지 1씩 빼기

2. N이 M의 배수라면 배수가 아니게 되거나 1이 될까지 N을 M으로 나눈다. 

 

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

def FromToOne(n,m):
    count = 0
    while n != 1:
        if n % m == 0:
            n = int(n / m)
            count += 1
        else: 
            n -= 1
            count += 1
    return count 

print(FromToOne(n,m))

 

(2) 정답 풀이 

# 단순하게 푸는 방법
n,k = map(int, input().split())
result = 0

while n >= k:
	while n % k != 0
    	n -= 1
        result += 1
     n //= k
     result +=1
     
 while n > 1:
 	n -= 1
    result += 1
    
 print(result)
 
 # 정답 예시 
n,k = map(int, input().split())
result = 0

while True:
	target = (n//k) * k 
    result += (n - target)
    n = target 
    if n < k:
    	break
     result += 1
     n //= k
 
result += (n - 1)
print(result)

 

정답 예시를 보면 최대한 반복 연산 횟수를 줄이는 모습을 볼 수 있다 예를 들어 10000 10001이 들어 왔다고 가정할 때 내 풀이는 1이 될 때까지 1을 9999번 빼야 한다. 그러나 정답 풀이는 그냥 m이 n보다 클 경우 10000-1을 결과에 더해서 한번의 연산을 진행한다.