[알고리즘] 그리디 실습 (숫자 카드 게임, 1이 될 때 까지)

[실습] 숫자 카드 게임

문제 설명

• N * M 의 카드가 있다.
• 뽑고자 하는 카드가 포함된 행을 선택한다.
• 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다.
• 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

 

게임이론에서 본 최소 극대 전략이다.

각 행마다 가장 작은 수를 찾은 뒤 그 중에서 가장 큰 수를 찾으면 되겠다.

 

N,M = map(int,input().split())

mylist = [[] for _ in  range(N)]

minmax = 0
for i in range(N):
    mylist[i] = list(map(int,input().split()))
    if minmax < min(mylist[i]):
        minmax = min(mylist[i])

print(minmax)

 

교재 보고 깨달은 내용

minmax = 0
for i in range(N):
	minmax = max(minmax,min(mylist[i]))

if 문 안쓰고 이렇게 한줄로 최댓값을 구할 수도 있네요

max 또는 min 함수에 인자를 두개 넣으면 이렇게 두 인자를 비교하여 더 큰값 또는 작은 값을 도출합니다.

---

[실습] 1이 될 때 까지 

문제 설명

• 1. N에서 1을 뺀다.
• 2. N을 K로 나눈다.
• 다음 두 과정 중 하나를 N이 1이 될 때 까지 수행한다.
• 단, 2번 과정은 N이 K로 나누어 질 때만 선택할 수 있다.

 

1번과 2번 중 우선시 되어야 하는건 2번이다. 그러면 최소 경로를 구할 수 있다.

 

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

 

교재 참고한 예시

N, K = map(int, input().split())

cnt = 0
while N!=1:
    if N % K == 0:
        N //= K
        cnt += 1
    else :
        cnt += N%K        # count를 먼저 해야한다.
        N -= N%K
print(cnt)

반복 횟수를 덜 돌리는 방향