๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 11660_๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 5

๋ฟŒ์•ผ._. 2022. 2. 22. 23:10

Silver I

๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/11660)

<๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 5>

๋ฌธ์ œ 

 

N×N๊ฐœ์˜ ์ˆ˜๊ฐ€ N×N ํฌ๊ธฐ์˜ ํ‘œ์— ์ฑ„์›Œ์ ธ ์žˆ๋‹ค. (x1, y1)๋ถ€ํ„ฐ (x2, y2)๊นŒ์ง€ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. (x, y)๋Š” xํ–‰ y์—ด์„ ์˜๋ฏธํ•œ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด, N = 4์ด๊ณ , ํ‘œ๊ฐ€ ์•„๋ž˜์™€ ๊ฐ™์ด ์ฑ„์›Œ์ ธ ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ์‚ดํŽด๋ณด์ž.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

์—ฌ๊ธฐ์„œ (2, 2)๋ถ€ํ„ฐ (3, 4)๊นŒ์ง€ ํ•ฉ์„ ๊ตฌํ•˜๋ฉด 3+4+5+4+5+6 = 27์ด๊ณ , (4, 4)๋ถ€ํ„ฐ (4, 4)๊นŒ์ง€ ํ•ฉ์„ ๊ตฌํ•˜๋ฉด 7์ด๋‹ค.
ํ‘œ์— ์ฑ„์›Œ์ ธ ์žˆ๋Š” ์ˆ˜์™€ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ์—ฐ์‚ฐ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

 

์ž…๋ ฅ

 

์ฒซ์งธ ์ค„์— ํ‘œ์˜ ํฌ๊ธฐ N๊ณผ ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ํšŸ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ํ‘œ์— ์ฑ„์›Œ์ ธ ์žˆ๋Š” ์ˆ˜๊ฐ€ 1ํ–‰๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๋„ค ๊ฐœ์˜ ์ •์ˆ˜ x1, y1, x2, y2 ๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, (x1, y1)๋ถ€ํ„ฐ (x2, y2)์˜ ํ•ฉ์„ ๊ตฌํ•ด ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค. ํ‘œ์— ์ฑ„์›Œ์ ธ ์žˆ๋Š” ์ˆ˜๋Š” 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. (x1 ≤ x2, y1 ≤ y2)

 

 

์ถœ๋ ฅ 

 

์ด M ์ค„์— ๊ฑธ์ณ (x1, y1)๋ถ€ํ„ฐ (x2, y2)๊นŒ์ง€ ํ•ฉ์„ ๊ตฌํ•ด ์ถœ๋ ฅํ•œ๋‹ค.

 

 

๋ฌธ์ œ ํ’€์ด

- my solution

import sys

if __name__=='__main__' :
    N,M=map(int,sys.stdin.readline().split())

    arr=[]
    for i in range(N): # ํ‘œ ์ž…๋ ฅ
        arr.append(list(map(int,sys.stdin.readline().split())))

    dp=[]
    for i in range(N): # ๊ตฌ๊ฐ„ ํ•ฉ
        temp=[]
        for j in range(N):
            if i==0:
                if j==0:
                    temp.append(arr[0][0])
                else:
                    temp.append(temp[-1]+arr[i][j])
            else:
                if j==0:
                    temp.append(dp[i-1][j]+arr[i][j])
                else:
                    temp.append(dp[i-1][j]+temp[-1]-dp[i-1][j-1]+arr[i][j])
        dp.append(temp)

    for i in range(M):
        section=list(map(int,sys.stdin.readline().split())) # [x1,y1,x2,y2]

        if section[0]-1!=0 or section[1]-1!=0:
            if section[0]-1!=0 and section[1]-1!=0:
                result=dp[section[2]-1][section[3]-1]-dp[section[2]-1][section[1]-2]-dp[section[0]-2][section[3]-1]+dp[section[0]-2][section[1]-2]
            elif section[0]-1==0:
                result = dp[section[2]-1][section[3]-1]-dp[section[2]-1][section[1]-2]
            elif section[1]-1==0:
                result=dp[section[2]-1][section[3]-1]-dp[section[0]-2][section[3]-1]
        else: #(1,1)๋ถ€ํ„ฐ(x2,y2)
            result = dp[section[2] - 1][section[3] - 1]

        print(result)

 

 

 

ํ‘œ๋ฅผ ์ž…๋ ฅ๋ฐ›์€ ํ›„ ๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ณ„์‚ฐํ•ด์ค€๋‹ค.

x1, y1, x2, y2๋ฅผ ์ž…๋ ฅ๋ฐ›์€ ํ›„ ์กฐ๊ฑด๋ณ„๋กœ ๊ตฌ๊ฐ„ ํ•ฉ ๊ณ„์‚ฐ ์‹์„ ๊ตฌํ˜„ํ•ด์ฃผ์—ˆ๋‹ค.

 

1) x1๊ณผ y1์ด 1์ด ์•„๋‹Œ ๊ฒฝ์šฐ 
  1-1) (1,1)๋ถ€ํ„ฐ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹Œ ๊ฒฝ์šฐ
  1-2) (1, y1) ~ (x2, y2)
  1-3) (x1,1) ~ (x2, y2)
2) (1,1) ~ (x2, y2)

 

์œ„์˜ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ„์–ด ๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ตฌํ–ˆ๋‹ค.

 

โ€ป ์„ค๋ช… ๋ถ€์กฑํ•œ ๊ฒƒ์€ ๋‹ค์Œ์— ๊ทธ๋ฆผ์œผ๋กœ ์„ค๋ช…ํ•˜๊ฒ ๋‹ค


์ƒ๊ฐ๐Ÿค”

 

๋ช‡ ๋‹ฌ ์ „์— ์‹คํŒจํ•˜์—ฌ ๋‹ค์‹œ ์‹œ๋„ํ•œ ๋ฌธ์ œ์˜€๋‹ค. ๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ตฌํ•œ ํ›„ (x1, y1)~(x2, y2) ์‚ฌ์ด์˜ ๊ตฌํ•œ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ์กฐ๊ฑด์‹์„

๊ตฌํ˜„ํ•˜๋Š” ๋ถ€๋ถ„์—์„œ ์ž˜๋ชป๋˜์—ˆ๋˜ ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์กฐ๊ธˆ ๋ณต์žกํ•˜๊ฒŒ ๊ตฌํ˜„ํ•œ ๊ฒƒ ๊ฐ™์€ ๋Š๋‚Œ์ด ์žˆ์ง€๋งŒ... ใ…Ž_ใ…Ž ํ†ต๊ณผ!