[카카오] 파괴되지 않은 건물 Python/DP/누적합

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

효율성!! 을 보는 문제여서 당연히 브루트포스는 아닐거란 예상은 했지만 그래도 꼭 하지말라고 하면 하고 싶은 법 나만 그래??????

def solution(board, skill):
    answer = 0
    def attack(a, b, c, d, degree):
        for i in range(a, c+1):
            for j in range(b, d+1):
                board[i][j] -= degree

    def save(a, b, c, d, degree):
        for i in range(a, c+1):
            for j in range(b, d+1):
                board[i][j] += degree
            
    n = len(board)
    m = len(board[0])
    
    for data in skill:
        if data[0] == 1:
            attack(data[1], data[2], data[3], data[4], data[5])
        else:
            save(data[1], data[2], data[3], data[4], data[5])
    for i in range(n):
        for j in range(m):
            if board[i][j] >= 1:
                answer += 1
    return answer

ㅋㅋㅋ 그리고 이렇게 효율성 꽝꽝꽝 나는걸 봐야 그제서야 또 머리를 굴리기 시작한다 
합이 일정하게 더해진다거나 빼지는 계산을 하는거니까 좌표들을 미리 계산해보면 되지 않을까? 라는 생각을 했다
그리고 결국 어려워서 해설을 참고 했는데 앗...! 싶었다 잊고 있었던 DP와 누적합 유형이었다 

array 가 2차원 배열일 때, (0,0) 부터 (i,j) 까지의 누적합을 구하면 된다. 

 

def solution(board, skill):
    answer = 0

    n = len(board)
    m = len(board[0])
    dp = [[0] * (m+1) for _ in range(n+1)]
    for type, r1, c1, r2, c2, degree in skill:
        if type == 1:
            degree = (-1)*degree
        dp[r1][c1] += degree
        dp[r2+1][c1] -= degree
        dp[r1][c2+1] -= degree
        dp[r2+1][c2+1] += degree
    # 누적합 계산
    for i in range(n):
        for j in range(m):
            dp[i+1][j] += dp[i][j]
    
    for i in range(n):
        for j in range(m):
            dp[i][j+1] += dp[i][j]

    for i in range(n):
        for j in range(m):
            if board[i][j] + dp[i][j] > 0 :
                answer += 1
    return answer

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

카카오의 해설 !