🔺 문제
20002번: 사과나무
N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다. 농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원
www.acmicpc.net
🧩 해결 아이디어
• 브루트포스 + 2차원 누적합
지난 주에 풀었던 문제가 생각났다.
그런데 이제 거기에 정사각형 조건만 추가된 버전!
[백준/JAVA] 1749번: 점수따먹기
🔺 문제 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운
bono039.tistory.com
1. 2차원 배열에 대한 2차원 누적합 배열을 구한다.
2. 2차원 누적합 배열을 돌며 정사각형 부분행렬을 구하고 이 중 최댓값을 구한다.
💥 유의사항
4중 for문 시 인덱스 주의
🔺 코드
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
|
import java.util.*;
import java.io.*;
public class Main {
static long max = Integer.MIN_VALUE;
static int N;
static int[][] board, dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
board = new int[N + 1][N + 1];
dp = new int[N + 1][N + 1];
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 1 ; j <= N ; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
// 2차원 배열에 대한 누적합
for(int i = 1 ; i <= N ; i++) {
for(int j = 1 ; j <= N ; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + board[i][j];
}
}
// 부분행렬 구하기
for(int x1 = 1 ; x1 <= N ; x1++) {
for(int y1 = 1 ; y1 <= N ; y1++) {
for(int x2 = x1 ; x2 <= N ; x2++) {
for(int y2 = y1 ; y2 <= N ; y2++) {
// 정사각형이 아니면 pass
if(x2 - x1 != y2 - y1) continue;
long ans = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
max = Math.max(max, ans);
}
}
}
}
System.out.println(max);
}
}
|
cs |
🔺 다른 풀이들
- 정사각형 처리를 이렇게 3중 for문으로 끝내신 분들도 많았다.
for(int k = 1; k <= n; k++) {
for (int i = k; i <= n; i++) {
for (int j = k; j <= n; j++) {
int temp = pre[i][j] - pre[i-k][j] - pre[i][j-k] + pre[i-k][j-k];
max = Math.max(max, temp);
}
}
}
💬 느낀 점
2차원 누적합 이제 좀 이해를 했다!!
누적합 문제 굿!!
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
✔ 2차원 누적합 배열 활용 유사문제
[백준/JAVA] 1749번: 점수따먹기
🔺 문제 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운
bono039.tistory.com
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
- 2차원 누적합 관련 그림 설명 굿!
[Prefix Sum] BOJ 20002 사과나무
🎈 백준 20002 사과나무 www.acmicpc.net/problem/20002 1~K 까지의 정사각형을 설정하고 과수원 범위만큼 완전탐색하여 최대 총이익을 구할 수 있다. => 또한, Prefix Sum을 이용하여 효율적으로 구현할 수 있
miin-z.tistory.com
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 2800번: 괄호 제거 (0) | 2023.12.09 |
---|---|
[백준/JAVA] 10799번: 쇠막대기 (0) | 2023.12.08 |
[백준/JAVA] 2346번: 풍선 터뜨리기 (0) | 2023.12.07 |
[백준/JAVA] 1749번: 점수따먹기 (0) | 2023.12.01 |
[백준/JAVA] 4920번: 테트리스 게임 (0) | 2023.12.01 |