์ด๊ฑด ๊ทธ๋ฅ ํด์ค๋ณด๊ณ ํ์๋ค.
๋ฌธ์ ์ค๋ช
[๋ณธ ๋ฌธ์ ๋ ์ ํ์ฑ๊ณผ ํจ์จ์ฑ ํ ์คํธ ๊ฐ๊ฐ ์ ์๊ฐ ์๋ ๋ฌธ์ ์ ๋๋ค.]
N x M ํฌ๊ธฐ์ ํ๋ ฌ ๋ชจ์์ ๊ฒ์ ๋งต์ด ์์ต๋๋ค. ์ด ๋งต์๋ ๋ด๊ตฌ๋๋ฅผ ๊ฐ์ง ๊ฑด๋ฌผ์ด ๊ฐ ์นธ๋ง๋ค ํ๋์ฉ ์์ต๋๋ค. ์ ์ ์ด ๊ฑด๋ฌผ๋ค์ ๊ณต๊ฒฉํ์ฌ ํ๊ดดํ๋ ค๊ณ ํฉ๋๋ค. ๊ฑด๋ฌผ์ ์ ์ ๊ณต๊ฒฉ์ ๋ฐ์ผ๋ฉด ๋ด๊ตฌ๋๊ฐ ๊ฐ์ํ๊ณ ๋ด๊ตฌ๋๊ฐ 0์ดํ๊ฐ ๋๋ฉด ํ๊ดด๋ฉ๋๋ค. ๋ฐ๋๋ก, ์๊ตฐ์ ํ๋ณต ์คํฌ์ ์ฌ์ฉํ์ฌ ๊ฑด๋ฌผ๋ค์ ๋ด๊ตฌ๋๋ฅผ ๋์ด๋ ค๊ณ ํฉ๋๋ค.
์ ์ ๊ณต๊ฒฉ๊ณผ ์๊ตฐ์ ํ๋ณต ์คํฌ์ ํญ์ ์ง์ฌ๊ฐํ ๋ชจ์์
๋๋ค.
์๋ฅผ ๋ค์ด, ์๋ ์ฌ์ง์ ํฌ๊ธฐ๊ฐ 4 x 5์ธ ๋งต์ ๋ด๊ตฌ๋๊ฐ 5์ธ ๊ฑด๋ฌผ๋ค์ด ์๋ ์ํ์
๋๋ค.
์ฒซ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (0,0)๋ถํฐ (3,4)๊น์ง ๊ณต๊ฒฉํ์ฌ 4๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (2,0)๋ถํฐ (2,3)๊น์ง ๊ณต๊ฒฉํ์ฌ 2๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ด 4๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋๋ ์ํ๊ฐ ๋ฉ๋๋ค.
์ธ ๋ฒ์งธ๋ก ์๊ตฐ์ด ๋งต์ (1,0)๋ถํฐ (3,1)๊น์ง ํ๋ณตํ์ฌ 2๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋์ด๋ฉด ์๋์ ๊ฐ์ด 2๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋์๋ค๊ฐ ๋ณต๊ตฌ๋๊ณ 2๊ฐ์ ๊ฑด๋ฌผ๋ง ํ๊ดด๋์ด์๋ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ง์ง๋ง์ผ๋ก ์ ์ด ๋งต์ (0,1)๋ถํฐ (3,3)๊น์ง ๊ณต๊ฒฉํ์ฌ 1๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ด 8๊ฐ์ ๊ฑด๋ฌผ์ด ๋ ํ๊ดด๋์ด ์ด 10๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋ ์ํ๊ฐ ๋ฉ๋๋ค. (๋ด๊ตฌ๋๊ฐ 0 ์ดํ๊ฐ ๋ ์ด๋ฏธ ํ๊ดด๋ ๊ฑด๋ฌผ๋, ๊ณต๊ฒฉ์ ๋ฐ์ผ๋ฉด ๊ณ์ํด์ ๋ด๊ตฌ๋๊ฐ ํ๋ฝํ๋ ๊ฒ์ ์ ์ํด์ฃผ์ธ์.)
์ต์ข ์ ์ผ๋ก ์ด 10๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋์ง ์์์ต๋๋ค.
๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ํ๋ด๋ 2์ฐจ์ ์ ์ ๋ฐฐ์ด board์ ์ ์ ๊ณต๊ฒฉ ํน์ ์๊ตฐ์ ํ๋ณต ์คํฌ์ ๋ํ๋ด๋ 2์ฐจ์ ์ ์ ๋ฐฐ์ด skill์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์ ์ ๊ณต๊ฒฉ ํน์ ์๊ตฐ์ ํ๋ณต ์คํฌ์ด ๋ชจ๋ ๋๋ ๋ค ํ๊ดด๋์ง ์์ ๊ฑด๋ฌผ์ ๊ฐ์๋ฅผ returnํ๋ solutionํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
์ ํ ์ฌํญ
- 1 ≤ board์ ํ์ ๊ธธ์ด (= N) ≤ 1,000
- 1 ≤ board์ ์ด์ ๊ธธ์ด (= M) ≤ 1,000
- 1 ≤ board์ ์์ (๊ฐ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋) ≤ 1,000
- 1 ≤ skill์ ํ์ ๊ธธ์ด ≤ 250,000
- skill์ ์ด์ ๊ธธ์ด = 6
- skill์ ๊ฐ ํ์ [type, r1, c1, r2, c2, degree]ํํ๋ฅผ ๊ฐ์ง๊ณ ์์ต๋๋ค.
- type์ 1 ํน์ 2์
๋๋ค.
- type์ด 1์ผ ๊ฒฝ์ฐ๋ ์ ์ ๊ณต๊ฒฉ์ ์๋ฏธํฉ๋๋ค. ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถฅ๋๋ค.
- type์ด 2์ผ ๊ฒฝ์ฐ๋ ์๊ตฐ์ ํ๋ณต ์คํฌ์ ์๋ฏธํฉ๋๋ค. ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋์ ๋๋ค.
- (r1, c1)๋ถํฐ (r2, c2)๊น์ง ์ง์ฌ๊ฐํ ๋ชจ์์ ๋ฒ์ ์์ ์๋ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ degree ๋งํผ ๋ฎ์ถ๊ฑฐ๋ ๋์ธ๋ค๋ ๋ป์
๋๋ค.
- 0 ≤ r1 ≤ r2 < board์ ํ์ ๊ธธ์ด
- 0 ≤ c1 ≤ c2 < board์ ์ด์ ๊ธธ์ด
- 1 ≤ degree ≤ 500
- type์ด 1์ด๋ฉด degree๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถฅ๋๋ค.
- type์ด 2์ด๋ฉด degree๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋์ ๋๋ค.
- type์ 1 ํน์ 2์
๋๋ค.
- ๊ฑด๋ฌผ์ ํ๊ดด๋์๋ค๊ฐ ํ๋ณต ์คํฌ์ ๋ฐ์ ๋ด๊ตฌ๋๊ฐ 1์ด์์ด ๋๋ฉด ํ๊ดด๋์ง ์์ ์ํ๊ฐ ๋ฉ๋๋ค. ์ฆ, ์ต์ข ์ ์ผ๋ก ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๊ฐ 1์ด์์ด๋ฉด ํ๊ดด๋์ง ์์ ๊ฑด๋ฌผ์ ๋๋ค.
์ ํ์ฑ ํ ์คํธ ์ผ์ด์ค ์ ํ ์ฌํญ
- 1 ≤ board์ ํ์ ๊ธธ์ด (= N) ≤ 100
- 1 ≤ board์ ์ด์ ๊ธธ์ด (= M) ≤ 100
- 1 ≤ board์ ์์ (๊ฐ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋) ≤ 100
- 1 ≤ skill์ ํ์ ๊ธธ์ด ≤ 100
- 1 ≤ degree ≤ 100
์ ํ์๊ฐ ์๋ด
- ์ ํ์ฑ ํ ์คํธ : 10์ด
- ํจ์จ์ฑ ํ ์คํธ : ์ธ์ด๋ณ๋ก ์์ฑ๋ ์ ๋ต ์ฝ๋์ ์คํ ์๊ฐ์ ์ ์ ๋ฐฐ์
ํจ์จ์ฑ ํ ์คํธ ์ผ์ด์ค ์ ํ ์ฌํญ
- ์ฃผ์ด์ง ์กฐ๊ฑด ์ธ ์ถ๊ฐ ์ ํ์ฌํญ ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
board | skill | result |
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] | [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] | 10 |
[[1,2,3],[4,5,6],[7,8,9]] | [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] | 6 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์ ์ถ๋ ฅ ์ #1
๋ฌธ์ ์์์ ๊ฐ์ต๋๋ค.
์ ์ถ๋ ฅ ์ #2
<์ด๊ธฐ ๋งต ์ํ>
์ฒซ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (1,1)๋ถํฐ (2,2)๊น์ง ๊ณต๊ฒฉํ์ฌ 4๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (0,0)๋ถํฐ (1,1)๊น์ง ๊ณต๊ฒฉํ์ฌ 2๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ง์ง๋ง์ผ๋ก ์๊ตฐ์ด ๋งต์ (2,0)๋ถํฐ (2,0)๊น์ง ํ๋ณตํ์ฌ 100๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋์ด๋ฉด ์๋์ ๊ฐ์ ์ํฉ์ด ๋ฉ๋๋ค.
์ด, 6๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋์ง ์์์ต๋๋ค. ๋ฐ๋ผ์ 6์ return ํด์ผ ํฉ๋๋ค.
ํ์ด
def solution(board, skill):
answer = 0
n = len(board)+1
m = len(board[0])+1
board_csum = [[0 for _ in range(m)] for _ in range(n)]
for sk in skill:
s_type, r1, c1, r2, c2, degree = sk
if s_type == 1:
degree *= -1
board_csum[r1][c1] += degree
board_csum[r1][c2+1] += degree * -1
board_csum[r2+1][c1] += degree * -1
board_csum[r2+1][c2+1] += degree
for i in range(n):
for j in range(1, m):
board_csum[i][j] += board_csum[i][j-1]
for j in range(m):
for i in range(1,n):
board_csum[i][j] += board_csum[i-1][j]
for i in range(n-1):
for j in range(m-1):
board[i][j] += board_csum[i][j]
if board[i][j] > 0:
answer += 1
return answer
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.07ms, 10.4MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.22ms, 10.4MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.44ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.79ms, 10.3MB)
ํ
์คํธ 6 ใ ํต๊ณผ (2.47ms, 10.3MB)
ํ
์คํธ 7 ใ ํต๊ณผ (1.63ms, 10.2MB)
ํ
์คํธ 8 ใ ํต๊ณผ (2.45ms, 10.5MB)
ํ
์คํธ 9 ใ ํต๊ณผ (2.96ms, 10.5MB)
ํ
์คํธ 10 ใ ํต๊ณผ (9.23ms, 10.4MB)
ํจ์จ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (880.75ms, 144MB)
ํ
์คํธ 2 ใ ํต๊ณผ (885.96ms, 144MB)
ํ
์คํธ 3 ใ ํต๊ณผ (895.76ms, 144MB)
ํ
์คํธ 4 ใ ํต๊ณผ (775.16ms, 144MB)
ํ
์คํธ 5 ใ ํต๊ณผ (669.92ms, 133MB)
ํ
์คํธ 6 ใ ํต๊ณผ (621.84ms, 133MB)
ํ
์คํธ 7 ใ ํต๊ณผ (711.07ms, 133MB)
- ๋์ด๋๊ฐ ๋์์ง์๋ก ํ์ด์ ๋ค์์ฑ์ด ์ค์ด๋ ๋ค.