[프로그래머스] 파괴되지 않은 건물 (누적합|Python)

2023. 10. 15. 19:40·Algorithm (PS)
728x90

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

이것이 누적합이다 !! 를 보여주는 문제이다 ㅋㅋㅋ 

단순하게 구현하면 시간초과가 나므로 누적합을 이용하여 degree 값을 미리 계산해두고 board에 더해주면 된다. 

def solution(board, skill):
    answer = 0
    n = len(board) # col 
    m = len(board[0]) # row 
    dp = [[0] * (m+1) for _ in range(n+1)]

    for t, r1, c1, r2, c2, degree in skill:
        if t == 1: # 공격 
            degree *= (-1) # minus 값으로 변경 
        # dp 에 표시해두기 
        dp[r1][c1] += degree # 영향 받기 시작하는 부분 
        dp[r1][c2+1] -= degree # degree 영향 범위 아닌 부분 
        dp[r2+1][c1] -= degree # 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
728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 1261번: 알고스팟 (Python) - 0-1 BFS 탐색  (0) 2023.10.29
[Programmers] 표현 가능한 이진트리 - Python  (1) 2023.10.23
[백준] 9466번: 텀 프로젝트 (DFS|Python) - 그래프에서 cycle을 찾기  (0) 2023.10.15
[백준] 10986번: 나머지 합 (Python) - 메모리 초과와 누적합  (0) 2023.09.29
[프로그래머스] 상담원 인원 - Python  (0) 2023.09.17
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 1261번: 알고스팟 (Python) - 0-1 BFS 탐색
  • [Programmers] 표현 가능한 이진트리 - Python
  • [백준] 9466번: 텀 프로젝트 (DFS|Python) - 그래프에서 cycle을 찾기
  • [백준] 10986번: 나머지 합 (Python) - 메모리 초과와 누적합
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • ansible
  • 클라우드
  • 쿠버네티스
  • 리눅스
  • 프로그래머스
  • dp
  • 파이썬
  • python
  • BFS
  • 빅데이터
  • SPARK
  • 데이터엔지니어
  • docker
  • dfs
  • 데이터엔지니어링
  • 백준
  • 데이터브릭스
  • 알고리즘
  • AWS
  • 백트래킹
  • 카카오코딩테스트
  • Kubernetes
  • Leetcode
  • EC2
  • Databricks
  • Swift
  • 운영체제
  • linux
  • 코딩테스트
  • 스파크

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[프로그래머스] 파괴되지 않은 건물 (누적합|Python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.