[Do-it 코딩 테스트] 004. 숫자의 합 구하기2(11660)

문제

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

---

코드

내가 작성한 코드

size, qnum = map(int, input().split())
a = [[0]* (size + 1)] #원본배열
d = [[0] * (size + 1) for _ in range(size + 1)] #원본배열의 합

# size만큼 입력값을 받아 2중배열을 만들어줌
for i in range(size):
    a_row = [0] + [int(x) for x in input().split()]
    a.append(a_row)

# 합 배열 구하기
for i in range(1, size + 1): #배열의 사이즈를 지정
    for j in range(1, size + 1): #배열의 사이즈를 지정
        d[i][j] = d[i][j-1] + d[i-1][j] - d[i-1][j-1] + a[i][j]

# 구간 합 배열로 질의에답변
for _ in range(qnum):
    x1, y1, x2, y2 = map(int, input().split())
    result = d[x2][y2] - d[x1-1][y2] - d[x2][y1-1] + d[x1-1][y1-1]
    print(result)

---

해석

입력예제

# 2차원 배열의 크기, 구간 합 질의의 개수 4 3 # 원본배열 1 ~ 5번째줄 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 #질의  2 2 3 4 3 4 3 4 1 1 4 4

size, qnum = map(int, input().split())
a = [[0]* (size + 1)] #원본배열
d = [[0] * (size + 1) for _ in range(size + 1)] #원본배열의 합

위 입력예제를 보면 2차원의 배열의 개수와 질의개수를 한번에 받아야한다 input()을 이용하여 '4 3' 을 입력해주고 split() 함수를 사용하여 공백을 기준으로 해당 문자열을 잘라 각 변수에 값을 넣어준다.

 

여기서 그냥 넣으면 문자열로 들어가기때문에 map()을 사용하여 int로 형변환을 해주었다.

 

아래 이미지처럼 초기 리스트를 만들어줘야해서

a = [[0]* (size + 1)] #원본배열
d = [[0] * (size + 1) for _ in range(size + 1)] #원본배열의 합

이중배열을 만들어주고 그 안에 값을 0을 넣은 후 * 위에 입력받은 size + 1을 해주었다.

 

size + 1을 해준 이유는 입력받은 값이 4인데 우리는 인덱스를 좌표로 사용하기 위해 + 1을 더해주었다.

인덱스는 0부터 시작한다.

# size만큼 입력값을 받아 2중배열을 만들어줌
for i in range(size):
    a_row = [0] + [int(x) for x in input().split()]
    a.append(a_row)

a배열을 아래 이미지처럼 만들어주기 위해  size만큼 입력값을 받아 a_row에 넣어주고 그  a_row값을 a에 append()를 해준다 그러면 아래 이미지처럼 2차원 배열이 만들어진다.

# 합 배열 구하기
for i in range(1, size + 1): #배열의 사이즈를 지정
    for j in range(1, size + 1): #배열의 사이즈를 지정
        d[i][j] = d[i][j-1] + d[i-1][j] - d[i-1][j-1] + a[i][j]

합을 구하는 공식은 예를 들어 [1][1] 부터 내가 구하고싶은  [2][4] 까지를 모두 더한 값이 합인데

여기서 [합배열 d]1번과 [합배열 d]2을 더하고 중복된 [합배열  d][1][3]  부분을  빼고 [원본배열 a]에 있는 [2][4]를 더하면 내가 구하고 싶은 [2][4]의 합이 나온다. 이 공식을 토대로 아래 수식이 나온다.

d[i][j] = d[i][j-1] + d[i-1][j] - d[i-1][j-1] + a[i][j]

# 구간 합 배열로 질의에답변
for _ in range(qnum):
    x1, y1, x2, y2 = map(int, input().split())
    result = d[x2][y2] - d[x1-1][y2] - d[x2][y1-1] + d[x1-1][y1-1]
    print(result)

구간합을 구하는 공식은 아래 이미지와 같다.

입력받은 값을 각x1,y1,x2,y2 라고 정의 했을 때 아래처럼 쓸 수 있다 여기서 d는 합배열리스트를 의미한다.

result = d[x2][y2] - d[x1-1][y2] - d[x2][y1-1] + d[x1-1][y1-1]