배열(Array)

백준 2578번 : 빙고

cepiloth 2018. 6. 17. 13:15
반응형

https://www.acmicpc.net/problem/2578


1. 문제 요약

5x5 칸의 빙고의 계수가 3개가 되면 횟수를 출력하는 문제


2. 알고리즘

입력 받은 수가 있다면 0 으로 초기화 한다. 1개의 빙고가 완성 된것을 의미한다.


가로 방향 빙고 검사 코드를 추가 한다.

1
2
3
4
5
6
7
8
9
10
11
for(int i=0; i<5;i++){
    int sum = 0;
 
    for(int j=0; j<5; j++) {    
        sum += table[i][j];
    }
 
    if (sum == 0) {
        count++;
    }
}
cs


세로 방향 검사를 추가 한다.

1
2
3
4
5
6
7
8
9
10
11
for(int i=0; i<5;i++){
  int sum = 0;
 
  for(int j=0; j<5; j++) {
    sum += table[j][i];
  }
 
  if (sum == 0) {
    count++;
  }
}
cs


대각 방향 검사를 추가 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cand = 0;
// 대각 방향 검사 [0][0] ~ [4][4]
for(int i=0; i<5;i++) {
  cand += table[i][i];
}
 
if (cand == 0) {
  count++;
}
 
cand = 0;
// 대각 방향 검사 [0][4] ~ [4][0]
for(int i=0; i<5;i++) {
  cand += table[0+i][5-1-i];
}
 
if (cand == 0) {
  count++;
}
cs


3. 코드

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
 
using namespace std;
 
int table[5][5];
void solve(int d) {
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++)
            if (d == table[i][j]) {
                table[i][j] = 0;
                break;
            }
    }
}
 
bool verify() {
    // row
    int count = 0;
    for(int i=0; i<5;i++){
        int sum = 0;
 
        for(int j=0; j<5; j++) {    
            sum += table[i][j];
        }
        
        if (sum == 0) {
            count++;
        }
    }
 
    for(int i=0; i<5;i++){
        int sum = 0;
        
        for(int j=0; j<5; j++) {
            sum += table[j][i];
        }
 
        if (sum == 0) {
            count++;
        }
    }
 
    int cand = 0;
    // 대각 방향 검사 [0][0] ~ [4][4]
    for(int i=0; i<5;i++) {
        cand += table[i][i];
    }
 
    if (cand == 0) {
        count++;
    }
 
    cand = 0;
    // 대각 방향 검사 [0][4] ~ [4][0]
    for(int i=0; i<5;i++) {
        cand += table[0+i][5-1-i];
    }
 
    if (cand == 0) {
        count++;
    }
 
    // 문제 끝까지 읽을 것 교차되는 영역이 3개 이상일 때만 bingo
    if (count >= 3) {
        return true;
    }
    return false;
}
 
int main() {
    
    std::ios::sync_with_stdio(false); cin.tie(0);
 
 
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++)
            cin >> table[i][j];
    }
 
    int sol = 0;
    for(int i=0; i<25; i++) {
        int cand; cin >> cand;
        solve(cand);
        if(verify()) {
            cout << i+1 << "\n";
            break;
        }
    }
    return 0;
}
cs

반응형