[알고리즘] BOJ 11660 - 구간 합 구하기 5(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

2 / 50

 

탐색

1 / 50

 

기초 동적 프로그래밍

2 / 50(NEW!)

 

투포인터

0 / 10

---

문제

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

11660번: 구간 합 구하기 5

---

문제 해결 아이디어

맨 처음 떠오르는 아이디어로 이중 for문을 돌려서 구간합을 구할 수도 있다.

→ 하지만 문제에서 테스트 케이스가 최대 100,000 이다.

→ 시간을 효율적으로 사용하도록 구현해야 한다.

→ 시간이 오래 걸리는 구간은 테스트 케이스의 수 때문인데,

→ 다행히 테스트 케이스마다 사용하는 표는 같다.

→ 하나를 구해놓고 이용해 먹자 ⇒ DP

 

(0, 0)과 (x, y)의 구간합을 나타내는 cache를 표의 가로 및 세로 길이만큼 초기화하자. 

그리고 그 cache를 사용해서 테스트케이스별로 구간합을 나타낸다.

 

(0, 0)부터 (x, y)의 구간합을 나타내는 cache 점화식:

cache[x][y] = cache[x][y-1] + cache[x - 1][y] - cache[x - 1][y - 1] + table[x][y] 

 

cache를 사용해서 (x1, y1)에서 (x2, y2)의 구간합 구하기:

answer = cache[x2][y2] - (cache[x1-1][y2] + cache[x2][y1 - 1] - cache[x1 - 1][y1 - 1])

---

구현

내 풀이

import sys
from copy import deepcopy
input = sys.stdin.readline

n, m = map(int, input().split())

# 표 입력 받기
table = [list(map(int, input().split())) for _ in range(n)]

# cache 초기화
cache = deepcopy(table)

for i in range(n) :
  for j in range(n) :
    if i == 0 and j == 0 :
      continue
    if not i == 0 :
      cache[i][j] += cache[i - 1][j]
    if not j == 0 :
      cache[i][j] += cache[i][j-1]
    if not (i == 0 or j == 0) :
      cache[i][j] -= cache[i-1][j-1]

# 테스트 케이스 입력받기
for _ in range(m) :
  x1, y1, x2, y2 = map(int, input().split())
  
  x1 -= 1
  y1 -= 1
  x2 -= 1
  y2 -= 1
  
  answer = cache[x2][y2]
  if not y1 == 0 :
    answer -= cache[x2][y1-1]
  if not x1 == 0 :
    answer -= cache[x1-1][y2]
  if not (x1 == 0 or y1 == 0) :
    answer += cache[x1-1][y1-1]
  print(answer)

 

다른 사람 풀이

import sys 
input = sys.stdin.readline

n, m = map(int,input().split())

table = [list(map(int, input().split())) for _ in range(n)]

cache = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        cache[i][j] = cache[i][j-1] + cache[i-1][j] - cache[i-1][j-1] + cache[i-1][j-1]

for _ in range(m):
    x1, y1, x2, y2 = map(int,input().split())

    answer = cache[x2][y2] - cache[x2][y1-1] - cache[x1-1][y2] + cache[x1-1][y1-1]
    print(answer)

나는 x와 y가 0일 때를 if문으로 고려해서 막 추가했는데,

단순히 인덱스를 1부터 시작하고, 인덱스 0은 다 0으로 초기화 해서

가장자리여도 상관이 없도록 구현했다.

 

그래서 훨씬 깔끔해보였음..

---

메모

• 2시간
  • 1시간 동안 아이디어를 못 생각해서 다른 사람 풀이에서 표로 그린 그림 잠깐 보고
  • 30분 동안 노트에 적어서 점화식 구하기
  • 30분 동안 구현....(DP 너무 어렵다..)

---