첫번째 접근
-
1차원 배열로도 문제를 해결할 수 있을 것으로 예상이 되지만, 인덱스 조절을 하는데에 반복적으로 연산의 과정을 거치게 될 거 같아서 2차원 배열로 푸는 것도 가독성 측면이나, 성능측면에서도 나쁘지 않은 선택이 될 거 같음
-
배열의 합이 $2^{31}-1$보다 작거나 같다의 조건은 배열의 합이 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
}
//초기화 잘하기
→ 이 흐름대로면 (1,2) (2,3)에서 올바른 값을 구할 수가 없음
while 안에서 인덱스에 대한 초기화가 계속 일어나더라도, (1,2) (1,3) (2,1) (2,2) (2,3)을 구하는 것이 아니라 (1,2) (1,3) (2,2) (2,3) 을 구하게 됨. 이 부분에 대해서 더 생각할 필요가 있어 보임
→ 문제를 잘못 이해했었는데 이 접근이 맞음
두번째 접근
-
첫번째 접근에서는 인덱스 접근을 이중루프문으로만 해결을 하려고 했음
→ 시작하는 좌표 즉, (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 초기화 조심
-
틀림...
→ i,j,x,y가 같은 행이거나 같은 값이면 올바른 논리가 적용되지 않음
(1,2) (1,2)에 대해 올바른 계산이 나오지 않음
세번째 접근
- 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"
}
→ 문제를 완전히 잘못 이해함.........
(1,3) (2,3) 을 입력 받으면,
빨강세모를 계산하는게 아니라 파란원을 계산해야함
결국 첫번째 접근이 정답이었음..