[03그리디] 3-3 숫자 카드 게임(p96~p98)

[예제3-3]

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

단, 게임의 룰을 지키며 카드를 뽑아야하고 룰은 다음과 같다.

 

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

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

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

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

 

예를 들어 3 x 3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자

여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종족으로 뽑는 카드는 2이다. 따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다.

카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

 

[입력 조건]

- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M 이 공백을 기준으로 하여 각각 자연수로 주어진다 (1 <= N, M <= 100)

- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

 

[출력 조건]

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

 

[입력 예시 1]

3 3
3 1 2
4 1 4
2 2 2

 

[출력 예시 1]

2

 

[입력 예시 2]

2 4
7 3 1 8
3 3 3 4

 

[출력 예시 2]

3

 

[코어 아이디어]

- 각 행마다 가장 작은 수를 찾은 뒤 그 수 중에서 가장 큰 수를 찾는 것

 

[소스 코드(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)

 

자 이게 정답인데, 입력되는 수가 어떻게 처리되는지 정확하게 이해가 안될수도 있다.

 

어떻게 이를 처리하는지에 대해 좀 더 알아보자. 

3 3
3 1 2
4 1 4
2 2 2

특히 위의 입력 예시를 들어보자면, 첫번째 행에서는 열이 하나 빈다. 어떻게 이런 입력이 가능한지에 대한 의문은 아래 for문에 답이 있다.

 

1. 첫 번째 줄의 input().split()의 결과는 ["3", "3"]이며, map(int, ) 처리로 (3, 3)형태로 바뀐다. 즉 n=3, m=3이 된다.

2. for i in range(n): 구문에 n=3이므로 총 for문이 3번 반복된다.

3. data, 즉 리스트형태로 여기서부터 총 3번동안 배열의 실제 원소들을 입력받는다. 순차적으로 3 1 2, 4 1 4, 2 2 2가 입력됨.

 

자 우선 여기까지 입력에 대한 설명이었다. 근데 어떻게 비교하는지도 궁금할 수 있다.

 

 

한 줄 입력 받음 → 예를 들어 [3, 1, 2]
→ min_value = 1
→ result = max(0, 1) → 1

 

다음 줄 [4, 1, 4]
→ min_value = 1
→ result = max(1, 1) → 1

 

다음 줄 [2, 2, 2]
→ min_value = 2
→ result = max(1, 2) → 2

 

이런식으로 각 라인의 최소값이 그 다음라인으로 넘어갔을때는 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)