백준 1184번

백준 1184번

접근 방식(알고리즘 분류)

• DP + Indexing

내 풀이

#한쪽 대각선만 생각했음
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

def arrSumRight(arr, a, b):
    sArr = [[0 for _ in range(n-b)] for _ in range(n-a)]
    aArr = [[0 for _ in range(n-b)] for _ in range(a)]
    sArr[0][0] = arr[a][b]
    aArr[a-1][0] = arr[a-1][b]
    resultS = [arr[a][b]]
    resultA = [arr[a-1][b]]

    # 교차점 기준 오른쪽 아래
    for i in range(n-a):
        for j in range(n-b):
            if i == 0 and j == 0:
                continue
            if i == 0:
                sArr[i][j] = sArr[i][j-1] + arr[i+a][j+b]
            elif j == 0:
                sArr[i][j] = sArr[i-1][j] + arr[i+a][j+b]
            else:
                sArr[i][j] = sArr[i-1][j] + sArr[i][j-1] + arr[i+a][j+b] - sArr[i-1][j-1]
            resultS.append(sArr[i][j])

    # 교차점 기준 오른쪽 위
    for i in range(a-1,-1,-1):
        for j in range(n-b):
            if i == a-1 and j == 0:
                continue
            elif i == a-1:
                aArr[i][j] = aArr[i][j-1] + arr[i][j+b]
            elif j == 0:
                aArr[i][j] = aArr[i+1][j] + arr[i][j+b]
            else:
                aArr[i][j] = aArr[i][j-1] + aArr[i+1][j] + arr[i][j+b] - aArr[i+1][j-1]
            resultA.append(aArr[i][j]) 

    return [resultS, resultA]

def arrSumleft(arr, a, b):
    sArr = [[0 for _ in range(b)] for _ in range(a)]
    aArr = [[0 for _ in range(b)] for _ in range(n-a)]
    sArr[a-1][b-1] = arr[a-1][b-1]
    aArr[0][b-1] = arr[a][b-1]
    resultS = [arr[a-1][b-1]]
    resultA = [arr[a][b-1]]

    # 교차점 기준 왼쪽 위
    for i in range(a-1, -1, -1):
        for j in range(b-1, -1, -1):
            if i == a-1 and j == b-1:
                continue
            if i == a-1:
                sArr[i][j] = sArr[i][j+1] + arr[i][j]
            elif j == b-1:
                sArr[i][j] = sArr[i+1][j] + arr[i][j]
            else:
                sArr[i][j] = sArr[i][j+1] + sArr[i+1][j] + arr[i][j] - sArr[i+1][j+1]
            resultS.append(sArr[i][j])

    #교차점 기준 왼쪽 아래
    for i in range(n-a):
        for j in range(b-1,-1,-1):
            if i == 0 and j == b-1:
                continue
            elif i == 0:
                aArr[i][j] = aArr[i][j+1] + arr[i+a][j]
            elif j == b-1:
                aArr[i][j] = aArr[i-1][j] + arr[i+a][j]
            else:
                aArr[i][j] = aArr[i][j+1] + aArr[i-1][j] + arr[i+a][j] - aArr[i-1][j+1]
            resultA.append(aArr[i][j])
    return [resultS, resultA]


answer = 0
for i in range(1,n):
    for j in range(1,n):
        leftSum = arrSumleft(arr,i,j)
        rightSum = arrSumRight(arr,i,j)

        #교차점 기준 왼쪽 위에랑 오른쪽 아래랑 비교
        for x in leftSum[0]:
            for y in rightSum[0]:
                if x == y:
                    answer += 1

        #교차점 기준 왼쪽 아래랑 오른쪽 위랑 비교
        for x in leftSum[1]:
            for y in rightSum[1]:
                if x == y:
                    answer += 1
print(answer)

풀이 설명

• 문제를 접근하는 방법을 찾기 어려웠다.
• 교차점을 기준으로 총 4군대로 나눠서 대각선 구역끼리 값을 비교했다.
• 시간효율을 위해서 구역에서의 합을 DP를 이용해서 구간합으로 비교했다.
• 구역마다 index를 다르게 처리해줘야 되는것이 많이 헷갈렸다 --> 특히 arr에 관련된 index 설정이 매우 어려웠다.
• 아직도 2차원배열에서 index 설정을 헤매는 내모습이 조금 한심했다..