반응형

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

 

5549번: 행성 탐사

상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 지도를 입력받고, sum[ i ][ j ] = sum[ i ][ j - 1 ] + sum[ i - 1 ][ j ] - sum[ i - 1 ][ j - 1 ] + arr[ i ][ j ]를 통해 구간합을 저장합니다.

 

2. 좌표 a, b, c, d를 입력받고,  ans = sum[ c ][ d ] - sum[ a - 1 ][ d ] - sum[ c ][ b - 1 ] + sum[ a - 1 ][ b - 1 ]을 통해 해당 좌표 내의 J, O, I의 개수를 구해 출력합니다. 

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
 
using namespace std;
 
struct node {
    int J, O, I;
};
 
node sum[1001][1001];
int M, N, K;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M >> N >> K;
 
    for (int i = 1; i <= M; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < N; j++) {
            sum[i][j + 1].J = sum[i][j].J + sum[i - 1][j + 1].J - sum[i - 1][j].J;
            sum[i][j + 1].O = sum[i][j].O + sum[i - 1][j + 1].O - sum[i - 1][j].O;
            sum[i][j + 1].I = sum[i][j].I + sum[i - 1][j + 1].I - sum[i - 1][j].I;
            if (temp[j] == 'J') {
                sum[i][j + 1].J++;
            }
            else if (temp[j] == 'O') {
                sum[i][j + 1].O++;
            }
            else {
                sum[i][j + 1].I++;
            }
        }
    }
 
    for (int i = 0; i < K; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        node ans = { 0 };
 
        ans.J = sum[c][d].J - sum[a - 1][d].J - sum[c][b - 1].J + sum[a - 1][b - 1].J;
        ans.O = sum[c][d].O - sum[a - 1][d].O - sum[c][b - 1].O + sum[a - 1][b - 1].O;
        ans.I = sum[c][d].I - sum[a - 1][d].I - sum[c][b - 1].I + sum[a - 1][b - 1].I;
 
        cout << ans.J << ' ' << ans.O << ' ' << ans.I << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13398번 - 연속합 2 (C++)  (0) 2023.09.17
[ 백준 ] 20183번 - 골목 대장 호석 - 효율성 2 (C++)  (0) 2023.09.16
[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12

+ Recent posts

티스토리툴바