Do it 알고리즘 코딩 테스트 - 4번

문제.

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

11660번: 구간 합 구하기 5

---

코드.

n,m = input().split()
N = int(n)
M = int(m)
A = [[0] * (N+1)]
D = [[0]*(N+1) for i in range(N+1)]
# for i in ragne(N+1):
#     tmp = [0]*(N+1)
#     D.append(tmp)
# D = [[0]*(N+1)] *(N+1)

sum1 =[]

for i in range(N):
    a = ['0'] + input().split()
    num = []
    for i in a:
        num.append(int(i))
    A.append(num)

# A에 리스트 입력완료 (0,0,0,0,0) (0,1,2,3,4,5) (0,2,3,4,5) (0,3,4,5,6) (0,4,5,6,7)

for i in range(1,N+1):
    D[i][0] = 0
    for j in range(1,N+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

print(A)
print(D)

for i in range(M):
    X1,Y1,X2,Y2 = map(int,input().split())
    sum = D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]
    sum1.append(sum)

print(sum1, type(sum1))

for i in sum1:
    print(i)

입력 값	출력 값
4 3 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	27 6 64

---

해석 및 풀이.

★ 이 문제는 숫자 N을 입력받아 N * N의 표를 만들어 입력받은 구간의 합을 M번 구하여 출력하는 프로그램을 만드는 문제입니다. 이때 처음 구성된 N * N의 표에 들어갈 숫자는 입력을 받아야 하며 합을 구해야하는 구간은 X, Y 좌표로 설정하여 구해야합니다.

n,m = input().split()
N = int(n)
M = int(m)
A = [[0] * (N+1)]
D = [[0]*(N+1) for i in range(N+1)]
# for i in ragne(N+1):
#     tmp = [0]*(N+1)
#     D.append(tmp)
# D = [[0]*(N+1)] *(N+1)

먼저 표를 만들 N값과 구간의 합을 구해야하는 횟수인 M값을 입력받을 input() 함수를 만들어줍니다. 문자열로 입력받아지기 때문에 int 를 써서 정수형으로 치환해주고 표를 만들 리스트를 만들어줍니다. 이때 리스트 A 는 구간합을 구해야하는 입력받은 숫자가 들어갈 표이며 리스트 D 는 구간의 합들을 계산해서 넣어줄 표입니다. 따라서 표의 구성은 아래와 같습니다.

* 처음 입력받은 숫자들을 나열한 표

sum1 =[]

for i in range(N):
    a = ['0'] + input().split()
    num = []
    for i in a:
        num.append(int(i))
    A.append(num)

# A에 리스트 입력완료 (0,0,0,0,0) (0,1,2,3,4,5) (0,2,3,4,5) (0,3,4,5,6) (0,4,5,6,7)

먼저 위에 있는 표처럼 리스트를 구성해야하는데 반복문을 이용하여 리스트로 한줄씩 넣어줍니다. 이때 입력값 제일 앞에 0을 추가해서 만들어 주는데 이유는 부분합을 구해서 넣어줄 리스트 D 를 구성할때 인덱스를 이용해서 계산을 진행해 주어야 하기 때문입니다. 부분합 리스트 표를 만드는 과정은 다음과 같습니다.

for i in range(1,N+1):
    D[i][0] = 0
    for j in range(1,N+1):
        D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

* 사진1 * 사진1	* 사진2	* 사진3
* 사진4	* 사진5	* 사진6

이렇게 인덱스를 이용하여 각 부분합을 반복문을 활용해 리스트 D 에 값을 넣어주는데 사진1 의 부분합을 구하기 위해서는 "사진2 - 사진4 - 사진5 + 사진3" 을 해줘야 하는데 인덱스를 고려했을때 위와 같은 수식이 나오기 때문입니다. 따라서 모든 부분을 구해주기 위해 인덱스 번호 까지 반복문을 돌려주게 되면 "사진6" 과 같은 결과를 얻을 수 있습니다. 이때 인덱스는 0번부터 시작하기 때문에 처음에 만들어준 리스트 A 내의 (0,0,0,0,0) 구간을 활용하여 1부터 넣어주게 됩니다.

for i in range(M):
    X1,Y1,X2,Y2 = map(int,input().split())
    sum = D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]
    sum1.append(sum)

print(sum1, type(sum1))

for i in sum1:
    print(i)

이제 부분합 리스트 D 까지 다 구성하였으므로 원하고자 하는 부분을 입력받아 구해주면 되는데 M번 만큼을 입력받기 위해 반복문을 이용해줍니다. 범위에 해당되는 X,Y 좌표를 리스트 D 의 데이터에 인덱스로 대입하여 공식을 이용해 출력할 임의의 리스트 sum1 에 넣어주고 이를 print로 출력해줍니다.