[그리디] 숫자 카드 게임

숫자 카드 게임

가장 높은 숫자를 뽑는 게임.

- NxM형태로 놓여있으며 N은 행 M 은 열을 뜻한다.

- 먼저 행을 선택한다

- 그 다음 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다.

 

입력 예시)

3 3

3 1 2

4 1 4

2 2 2

 

출력 예시)

2

 

입력 예시)

2 4

7 3 1 8

3 3 3 4

 출력 예시)

3

 

 

나의 코드

n,m=map(int, input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
res=[0]*n

for i in range(n):
    res[i]=min(arr[i])

print(max(res))

가장 높은 숫자와 가장 낮은 숫자 라는 단어가 보여 바로 그리디임을 직감했다.

또한 결국 출력 값은 '모든 행들의 최소값들 중에서 최대값' 이므로 정당성에 힘이 더 실렸다.

 

 

정답 코드

# N, M을 공백을 기준으로 구분하여 입력 받기
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) # 최종 답안 출력

그리디 알고리즘의 정석 답게

한 행씩 입력 받아 가장 작은 수를 min 함수로 찾은 뒤 그 값을  다시 현재까지의 가장큰 수인 result와 비교하여 가장 큰 값을 다시 result로 저장해 준 풀이이다.