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

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14647

문제 출처

  • 제1회 천하제일 코딩대회 예선 C번

시간복잡도

  • 최대 숫자의 자리수를 d라고 하면, O(dn2)

풀이

  1. 정수에서 9의 개수를 구하는 함수 split을 만듭니다.
  2. n, m을 입력받습니다.
  3. 빙고판을 입력받습니다.
  4. 입력을 받으면서 각 행, 열에서 9의 개수와 판 전체의 9의 개수도 같이 구합니다. (미리 선언해놓은 split 함수 사용)
  5. 각각의 행, 열에 포함된 9의 개수 중 최대값을 찾습니다.
  6. (전체 개수 - 최대값) 을 출력합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int n, m, all, maximum;
int arr[510][510];
int sumi[510], sumj[510];

int split(int n){
	int cnt = 0;
	while(n > 0){
		if(n%10 == 9) cnt++;
		n /= 10;
	}
	return cnt;
}

int main(){
	cin >> n >> m;

	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> arr[i][j];
			sumi[i] += split(arr[i][j]);
			sumj[j] += split(arr[i][j]);
			all += split(arr[i][j]);
		}
	}

	for(int i=0; i<n; i++){
		if(sumi[i] > maximum) maximum=sumi[i];
	}

	for(int j=0; j<m; j++){
		if(sumj[j]>maximum) maximum=sumj[j];
	}
	printf("%d", all-maximum);
}