728x90
반응형
1. 문제
https://www.acmicpc.net/problem/23247
2. 풀이
사각형의 양 끝 점을 잡아서 사각형의 숫자들을 다 더하는 것을 반복하는 방법을 떠올리는 것이 가장 쉽다.
그러나 이 방법은 양 끝점을 잡는 4중 포문, 사각형의 숫자들을 다 더하는 2중 포문으로 6중포문이 생기므로 현재 입력에서는 무조건 시간초과가 난다. 대신, 2차원 누적합을 아이디어를 사용하면 해결할 수 있다.
3. 코드
#include <iostream>
using namespace std;
int prefixSum[310][310], board[310][310];
int m, n, ans;
// 23247
/*
1) 완전 탐색으로 사각형의 양 끝점을 잡아서 만들어보는 방법은 최대 6중포문이 생기므로 무조건 시간초과가 난다.
2) 2차원 누적합을 이용해 풀어보자
prefixSum[a][b] : (1, 1) ~ (a, b) 까지의 누적합
prefixSum[a][b] = prefixSum[a-1][b] + prefixSum[a][b-1] - prefixSum[a-1][b-1] + data[a][b] <- 이 식은 그림을 그려보면 쉽다.
*/
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> m >> n;
// 입력
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
cin >> board[i][j];
// 누적 합 계산
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + board[i][j];
// for(int i=1; i<=m; i++) {
// for(int j=1; j<=n; j++)
// cout << prefixSum[i][j] << " ";
// cout << "\n";
// }
// (i, j) ~ (k, l) 누적합을 구함. (k, l)이 증가하는 방향이니 만약 10을 넘으면 중지
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++) {
for(int k=i; k<=m; k++) {
for(int l=j; l<=n; l++) {
int rectSum = prefixSum[k][l] - prefixSum[k][j-1] - prefixSum[i-1][l] + prefixSum[i-1][j-1];
if(rectSum == 10) ans++;
if(rectSum > 10) break;
}
}
}
}
cout << ans;
return 0;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 13335] 트럭 [C++] (0) | 2023.10.14 |
---|---|
[백준 - 20040] 사이클 게임 [C++] (0) | 2023.10.13 |
[백준 - 1780] 종이의 개수 [C++] (0) | 2021.03.15 |
[백준 - 1051] 숫자 정사각형 [C++] (0) | 2021.03.14 |
[백준 - 15988] 1, 2, 3 더하기 3 [C++] (0) | 2021.03.14 |