[Gold V] 행성 탐사 - 5549
성능 요약
메모리: 81220 KB, 시간: 624 ms
분류
누적 합
제출 일자
2024년 6월 8일 13:07:06
문제 설명
상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다.
상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다.
지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 크기 M과 N이 주어진다. (1 ≤ M, N ≤ 1000)
둘째 줄에 정인이가 만든 조사 대상 영역의 개수 K가 주어진다. (1 ≤ K ≤ 100000)
셋째 줄부터 M개 줄에는 상근이가 보낸 지도의 내용이 주어진다.
다음 K개 줄에는 조사 대상 영역의 정보가 주어진다. 정보는 네 정수 a b c d로 이루어져 있다. 구역은 직사각형 모양 이며, 왼쪽 위 모서리의 좌표가 (a, b) 오른쪽 아래 모서리의 좌표가 (c, d)이다.
출력
각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력한다.
접근 방법
1. 각 정글, 바다, 얼음마다 누적합을 이용해서 계산 속도를 향상시킨다면 1초안에 가능하다.
-> 값을 입력받으면서 누적합을 계산 해준다 M * N (1000 * 1000) + K만큼 상수시간이 걸린다.(100000)
2. 누적합을 구하는 공식 : map[i][j] = map[i-1][j] + map[i][j-1] -map[i-1][j-1]
3. 그 후 범위만큼 구하는 공식 : map[eX][eY] - map[sX-1][eY] - map[eX][sY-1] + map[sX-1][sY-1]
-> 전체 범위에서 해당 범위에 포함되지 않는 구간은 제외하면서 두번 감소되는 구간(map[0][0] ~ map[sX-1][sY-1)은 다시 한번 더해준다.
풀이 코드
import java.io.*;
import java.util.StringTokenizer;
/**
* 문제: BOJ_5549_G5_행성탐사
* 메모리: 81220KB
* 시간: 624ms
* 접근 방법
* 1. 각 정글, 바다, 얼음마다 누적합을 이용해서 계산 속도를 향상시킨다면 1초안에 가능하다.
* -> 값을 입력받으면서 누적합을 계산 해준다 M * N (1000 * 1000) + K만큼 상수시간이 걸린다.(100000)
* 2. 누적합을 구하는 공식 : map[i][j] = map[i-1][j] + map[i][j-1] -map[i-1][j-1]
* 3. 그 후 범위만큼 구하는 공식 : map[eX][eY] - map[sX-1][eY] - map[eX][sY-1] + map[sX-1][sY-1]
* -> 전체 범위에서 해당 범위에 포함되지 않는 구간은 제외하면서 두번 감소되는 구간(map[0][0] ~ map[sX-1][sY-1)은 다시 한번 더해준다.
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
// Input
int[][][] map = new int[3][N + 1][M + 1];
for (int i = 1; i <= N; i++) {
String input = br.readLine();
for (int j = 1; j <= M; j++) {
for (int k = 0; k < 3; k++) {
map[k][i][j] = map[k][i - 1][j] + map[k][i][j - 1] - map[k][i - 1][j - 1];
}
char ch = input.charAt(j - 1);
if (ch == 'J') {
map[0][i][j]++;
} else if (ch == 'O') {
map[1][i][j]++;
} else {
map[2][i][j]++;
}
}
}// Input End
StringBuilder sb = new StringBuilder();
int sX, sY, eX, eY, jungle, ocean, ice;
for (int i = 1; i <= K; i++) {
st = new StringTokenizer(br.readLine());
sX = Integer.parseInt(st.nextToken());
sY = Integer.parseInt(st.nextToken());
eX = Integer.parseInt(st.nextToken());
eY = Integer.parseInt(st.nextToken());
jungle = map[0][eX][eY] - map[0][sX - 1][eY] - map[0][eX][sY - 1] + map[0][sX - 1][sY - 1];
ocean = map[1][eX][eY] - map[1][sX - 1][eY] - map[1][eX][sY - 1] + map[1][sX - 1][sY - 1];
ice = map[2][eX][eY] - map[2][sX - 1][eY] - map[2][eX][sY - 1] + map[2][sX - 1][sY - 1];
sb.append(jungle).append(' ').append(ocean).append(' ').append(ice).append('\n');
}
System.out.println(sb);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 1082번 : 방 번호 Gold3(골드3) - JAVA[자바] (1) | 2024.06.13 |
---|---|
[백준] 1113번 : 수영장 만들기 Gold1(골드1) - JAVA[자바] (0) | 2024.06.11 |
[백준] 3687번 : 성냥개비 Gold2(골드2) - JAVA[자바] (1) | 2024.06.07 |
[백준] 14676번 : 영우는 사기꾼? Gold3(골드3) - JAVA[자바] (1) | 2024.06.06 |
[백준] 1484번 : 다이어트 Gold5(골드5) - JAVA[자바] (1) | 2024.06.05 |