문제접근
1.
첫번째 접근
•
1차원 배열로도 문제를 해결할 수 있을 것으로 예상이 되지만, 인덱스 조절을 하는데에 반복적으로 연산의 과정을 거치게 될 거 같아서 2차원 배열로 푸는 것도 가독성 측면이나, 성능측면에서도 나쁘지 않은 선택이 될 거 같음
•
배열의 합이 보다 작거나 같다 의 조건은 배열의 합이 int형의 범위를 넘지 않음에 대해 힌트를 준 것으로 판단
•
배열을 입력 받고 i, j, x, y를 통해서 (i, j) 부터 (x, y) 까지 인덱스 접근을 하나하나하여 누적합을 구하면 될듯
최악의 경우, N = 300 M = 300 K = 10000인 상황에서도 연산은 10억을 넘지 않기 때문에 시간 제한도 괜찮을 것으로 판단
•
가독성을 위하여 인덱스는 (0, 0)이 아닌 (1, 1)부터 시작
//pseudo code
cin >> n,m
cin >> 2차원배열
while(k--)
{
cin >> i,j,x,y
while( <= n && <= x)
while( <= m && <= y)
sum += '2차원 배열의 해당인덱스의 값'
cout << sum
}
//초기화 잘하기
C++
복사
→ 이 흐름대로면 (1,2) (2,3)에서 올바른 값을 구할 수가 없음
while 안에서 인덱스에 대한 초기화가 계속 일어나더라도, (1,2) (1,3) (2,1) (2,2) (2,3)을 구하는 것이 아니라 (1,2) (1,3) (2,2) (2,3) 을 구하게 됨. 이 부분에 대해서 더 생각할 필요가 있어 보임
→ 문제를 잘못 이해했었는데 이 접근이 맞음
2.
두번째 접근
•
첫번째 접근에서는 인덱스 접근을 이중루프문으로만 해결을 하려고 했음
→ 시작하는 좌표 즉, (i,j)에 대한 접근을 하는 루프문 하나와 중간에 대한 접근 그리고 마지막 (x,y)를 접근하는 루프문 3개로 만들어서접근을 진행을 하면 될듯
//pseudo code
cin >> n,m
cin >> 2차원배열
while(k--)
{
cin >> i,j,x,y
while (j <= m)
//첫좌표에 해당하는 같은 행들에 대한 연산
while (i + 1 <= x - 1) // 그 다음 행들부터 마지막 좌표가 포함된 행 전까지에 대한 연산
while ( <= m)
//첫좌표와 마지막좌표 사이의 행들에 대한 연산
while ( <= y)
//마지막좌표에 해당하는 같은 행들에 대한 연산
cout << sum
}
//index 초기화 조심
C++
복사
•
틀림...
→ i,j,x,y가 같은 행이거나 같은 값이면 올바른 논리가 적용되지 않음
(1,2) (1,2)에 대해 올바른 계산이 나오지 않음
3.
세번째 접근
•
1차원으로 접근하는 방식이 생각보다 나쁘지 않을듯
•
입력값을 1차원에 저장을 해두고 예를 들어 (2,3)에 접근을 하고 싶으면 2*3=6, 즉 1차원 배열의 6번째에 접근을 하면 되는것
//pseudo code
cin >> n , m , k
cin >> 1차원
while(k--)
{
cin >> i,j,x,y
while (i*j <= x*y)
누적합
cout << 누적합 << "\n"
}
C++
복사
→ 문제를 완전히 잘못 이해함.........
(1,3) (2,3) 을 입력 받으면,
빨강세모를 계산하는게 아니라 파란원을 계산해야함
결국 첫번째 접근이 정답이었음..
놓쳤던 부분
•
문제를 잘못 이해해서 잘못 접근함
코드
2416 KB
572 ms
#include <iostream>
#include <vector>
int n,m,k;
std::vector<std::vector<int> > input_arr;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int i,j;
i = 0;
std::cin >> n >> m;
input_arr.resize(n + 1, std::vector<int>(m + 1, 0));
while (++i <= n)
{
j = 0;
while (++j <= m)
std::cin >> input_arr[i][j];
}
std::cin >> k;
}
void solution()
{
int i, j, x, y;
int row, col;
int sum;
while (k--)
{
sum = 0;
std::cin >> i >> j >> x >> y;
row = i - 1;
while (++row <= n && row <= x)
{
col = j - 1;
while (++col <= m && col <= y)
sum += input_arr[row][col];
}
std::cout << sum << "\n";
}
}
int main(void)
{
input_setting();
input();
solution();
return (0);
}
C++
복사
