[CH3 그리디] 숫자 카드 게임

숫자 카드 게임

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

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

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

 

[입력 조건]

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 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

 

---

문제 풀이)

• 그리디 알고리즘 유형의 무네는 문제 해결을 위한 아이디어를 떠올렸으면 정답을 찾을 수 있다
• 이 문제를 푸는 아이디어는 '각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수'를 찾는 것이다
• 문제는 길지만 아이디어는 쉬운 편이다!
• 입력으로 들어오는 수가 10,000 이하니까 단순하게 각 행에서 가장 작은 수를 찾은 다음 그 수 중에서 가장 큰 수를 찾는 방식으로 문제를 해결하면 된다

---

 

파이썬 코드)

#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(min_value, result)

print(result)

min 함수를 이용해서 구현하였다!

 

 

C++ 코드)

#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
    int n,m;
    int min=10001,result=0;
    int arr[100][100]={0};
    
    cin>>n>>m; //n,m 입력받기
    
    for(int i=0;i<n;i++) //카드 배열로 입력 받기
    {
        for(int j=0;j<m;j++)
        {
            cin>>arr[i][j];
        }
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(min>arr[i][j])
            {
                min=arr[i][j];
            }
        }
        if(result<min)
        {
            result=min;
        }
        min=10001; //행마다 min 초기화
    }
    printf("%d\n",result);
    return 0;
}

입력 받는 걸로 생각하면 배열에 저장안하고 그 때마다 비교하고 싶었지만, 프로그래머스같은 코테에서는 주로 이미 입력값이 배열로 주어지니까 그냥 반복문 2개로 구현했다!

 

---

 

시험기간이기도 하고 졸리니까 한 문제만 풀어야지,,

종강하면 하루에 아주 그냥 한 챕터씩 풀어줄게!

빠잉~