๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ
- DP ์๊ณ ๋ฆฌ์ฆ์ ์ํจ
- ์ ์ฒ๋ฆฌ๋ฅผ ํ ํ์๋ 1์ฐจ์ใป2์ฐจ์ ๋ฐฐ์ด์ ํฉ์ ๐(๐) ๋ง์ ๊ตฌํ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ
1์ฐจ์ ๋ฐฐ์ด์์ ๋์ ํฉ
- ์์ ์์ด๋ ์ ๋์ํจ
- Dp ํ
์ด๋ธ ์ค๊ณ
- psum[n]: 1~n๋ฒ์งธ ์์๊น์ง์ ํฉ
- ๊ด๊ณ์
- psum[n] = psum[n-1] + arr[n]
- a๋ถํฐ b๊น์ง ์์์ ํฉ์ ๊ตฌํ๋ ๋ฐฉ๋ฒ
- psum[b] - psum[a-1]
2์ฐจ์ ๋ฐฐ์ด์์ ๋์ ํฉ
- 2์ฐจ์ ๋ฐฐ์ด์ ์ธ๋ก ๊ธธ์ด๋ฅผ N, ๊ฐ๋ก ๊ธธ์ด๋ฅผ M์ด๋ผ๊ณ ํ ๋, ๐(๐๐) ์ ์ ์ฒ๋ฆฌ๋ฅผ ์ํํ๋ฉด ๋จ
- DP ํ
์ด๋ธ ์ค๊ณ
- psun[n][m]: (1, 1)๋ถํฐ (n, m)๊น์ง์ 2์ฐจ์ ํฉ
- ๊ด๊ณ์
- psum[n][m] = (psum[n][m-1] + psum[n-1][m] - psum[n-1][m-1]) + arr[n]
- (sy, sx)๋ถํฐ (ey, ex)๊น์ง์ 2์ฐจ์ ํฉ ๊ตฌํ๋ ๋ฐฉ๋ฒ
- psum[ey][ex] - (psum[ey][sx-1] + psum[sy-1][ex] - psum[sy-1][sx-1])
๋์ ํฉ ์๊ณ ๋ฆฌ์ฆ์ ์ธ์ ์ธ๊น!?
- 1์ฐจ์ ๋ฐฐ์ด์ ๋์ ํฉ
- ์ฐ์๋ ํฉ์ ๊ตฌ๊ฐ์ ์ฌ๋ฌ ๋ฒ ๊ตฌํด์ผ ํ ๋
- ๐(๐³) → ๐(๐²)
- 2์ฐจ์ ๋ฐฐ์ด์ ๋์ ํฉ
- (์ง์ฌ๊ฐํ ๋ชจ์์) 2์ฐจ์ ํฉ์ ์ฌ๋ฌ ๋ฒ ๊ตฌํด์ผ ํ ๋
- ๐((๐๐)³) → ๐((๐๐)²)
'์๊ณ ๋ฆฌ์ฆ ๐' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ (0) | 2024.07.18 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ (0) | 2024.07.18 |
[์๊ณ ๋ฆฌ์ฆ] ๋ธ๋ฃจํธ ํฌ์ค ์๊ณ ๋ฆฌ์ฆ (0) | 2024.07.18 |
[์๊ณ ๋ฆฌ์ฆ] ์์ด ์๊ณ ๋ฆฌ์ฆ & ์กฐํฉ ์๊ณ ๋ฆฌ์ฆ (0) | 2024.07.18 |
[์๊ณ ๋ฆฌ์ฆ] DP ์๊ณ ๋ฆฌ์ฆ (& ์ฌ๊ทํจ์) (0) | 2024.07.18 |