[백준][누적합] 5549. 행성 탐사

5549. 행성 탐사

5549번: 행성 탐사

 

 

• 내 풀이- fail
  • 메모리초과
  • accumulate 누적합 함수써서 각 행별 문자열 누적합 구한후 그 갯수를 다시 저장
  • 같은 행끼리 범위해당되는거 빼서 구함

# 정글, 바다, 얼음
from itertools import accumulate

n, m = map(int, input().split())
k = int(input())
graph = [list(input().rstrip()) for _ in range(n)]
tmp = [list(accumulate(graph[i])) for i in range(n)]

result = [[] for _ in range(n)]
for i in range(n):
    tmp = list(accumulate(graph[i]))

    for t in tmp:
        cnt = []
        cnt.append(t.count('J'))
        cnt.append(t.count('O'))
        cnt.append(t.count('I'))
        result[i].append(cnt)

answer = []
for i in range(k):
    sx, sy, ex, ey = map(int, input().split())
    cnt = [0, 0, 0]
    for j in range(sx-1, ex):
        for k in range(3):
            if sy == 1:
                cnt[k] += result[j][ey-1][k]
            else:
                cnt[k] += result[j][ey-1][k]-result[j][sy-2][k]

    answer.append(cnt)

for i in range(n):
    print(*answer[i])

 

 

• 다른 사람 풀이
  • 일단 누적합사용할 때 0번째 행, 0번째 열 하나씩 추가해줘서 늘려주기
  • 정글,바다, 얼음 부분을 다 더해줘야함

jsum[i][j] = jsum[i][j-1] + jsum[i-1][j] - jsum[i-1][j-1] + graph[i][j] 

1 2
3 4 이면
누적합 만들때 : 3+2-1+4
해당 위치 값 구할 때: 4 - 3-2 +1

 

# 정글, 바다, 얼음
n, m = map(int, input().split())
k = int(input())
graph = [[0 for _ in range(m+1)]]
graph += [[0]+list(input().rstrip()) for _ in range(n)]
result = [[] for _ in range(n)]

result = [[[0, 0, 0] for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        result[i][j][0] = result[i][j-1][0] + result[i-1][j][0] - result[i-1][j-1][0]
        result[i][j][1] = result[i][j-1][1] + result[i-1][j][1] - result[i-1][j-1][1]
        result[i][j][2] = result[i][j-1][2] + result[i-1][j][2] - result[i-1][j-1][2]
        if graph[i][j] == 'J':
            result[i][j][0] += 1
        elif graph[i][j] == 'O':
            result[i][j][1] += 1
        elif graph[i][j] == 'I':
            result[i][j][2] += + 1


answer = []
for i in range(k):
    sx, sy, ex, ey = map(int, input().split())
    tmp = []
    for j in range(3):
        tmp.append(result[ex][ey][j]-result[ex][sy-1][j] - result[sx-1][ey][j]+result[sx-1][sy-1][j])
    answer.append(tmp)


for i in range(k):
    print(*answer[i])