백준 14647번 준오는 조류혐오야!!

문제 링크입니다: https://www.acmicpc.net/problem/14647

간단한 탐색 문제였습니다.

알고리즘은 아래와 같습니다.

1. 각 숫자에 포함된 9의 개수를 파악하는 함수를 정의합니다.

2. 빙고판을 입력 받을 때 숫자로 입력받지 않고 각 숫자의 9의 개수로 입력받습니다.

-> 이 때, 9가 최대로 많이 있는 열도 파악합니다.

-> 모든 9의 개수를 파악합니다.

3. 9가 최대로 많이 있는 행을 파악합니다.

4. 2번에서 구한 모든 9의 개수 - max(2번에서 구한 열, 3번에서 구한 행)이 정답입니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 500;

 

int N, M;

int bingo[MAX][MAX];

 

//9의 개수 파악

int findNine(int num)

{

        int result = 0;

        while (num)

        {

                 if (num % 10 == 9)

                         result++;

                 num /= 10;

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        int nine = 0;

        int rowMax = 0, colMax = 0;

        //빙고판 전체 9의 개수 파악

        //9가 최대로 있는 열 파악

        for (int i = 0; i < N; i++)

        {

                 int colSum = 0;

                 for (int j = 0; j < M; j++)

                 {

                         int temp;

                         cin >> temp;

 

                         bingo[i][j] = findNine(temp);

                         colSum += bingo[i][j];

                         nine += bingo[i][j];

                 }

                 colMax = max(colMax, colSum);

        }

 

        //9가 최대로 있는 행 파악

        for (int i = 0; i < M; i++)

        {

                 int rowSum = 0;

                 for (int j = 0; j < N; j++)

                         rowSum += bingo[j][i];

                 rowMax = max(rowMax, rowSum);

        }

 

        //최대 행 혹은 열을 빼줌

        cout << nine - max(colMax, rowMax) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~