✓

태그:

CLASS 4 ESSENTIAL

설마 모든 원소를 돌아다니면서 합을 구할 건가요? 그냥 합을 저장하는건 어때요?

풀이 비스무리한거 보기

n×n 행렬의 일정 범위에 속하는 모든 원소의 합을 구하는 문제입니다. 문제의 조건에 따르면 최대 크기가 1024×1024이고, 만약 합을 구하는 범위가 (1, 1) 에서 (1024, 1024)로 100000번 호출된다고 생각하면 시간 초과는 당연한 결과가 됩니다. 따라서 주어진 행렬을 효율적으로 저장하는 방법에 대해 생각해야 하는데, 어차피 지금 구하는게 합인거 그냥 (1, 1)에서 (x, y)까지의 합을 저장해놓고 이걸 이용해서 답을 구하는 방법을 생각할 수 있겠습니다.

먼저 행렬을 저장할 때입니다. (i, j)를 입력받으면 여기에 (i - 1, j)를 더하고, (i, j - 1)열 원소를 더하고, (i - 1, j - 1)열 원소를 뺍니다. 이렇게 하면 1행 1열부터 i행 j열까지의 원소의 합을 구할 수 있습니다. 식이 이렇게 되는 이유는 다음과 같습니다. (1, 1)부터 (i, j)까지의 원소 중 (i, j)를 제외한 합은

• (1, 1) ~ (i - 1, j)의 합
• (1, 1) ~ (i, j - 1)의 합
• 에서 두 범위의 겹치는 부분인 (1, 1) ~ (i - 1, j - 1)을 차감

한 값이 됩니다.

이제 다시 출력할 때입니다. (x1, y1)에서 (x2, y2)로 범위가 주어지면 다시 같은 방법으로 값을 구합니다.

• (1, 1) ~ (x2, y2)의 합
• 에서 (1, 1) ~ (x2, y1 - 1)의 합을 차감
• 에서 (1, 1) ~ (x1 - 1, y2)의 합을 차감
• 위의 두 범위의 겹치는 부분인 (1, 1) ~ (x1 - 1, y1 - 1)은 다시 가산

하면 원하는 출력값이 나옵니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-10 10:54:51

---