백준 25682번 : 체스판 다시 칠하기 2[C#]

단계별로 문제를 풀면 체스판 다시 칠하기 1은 브루트포스로 풀었는데요. 달라진건 보드판의 크기가 커지고, 시간제한도 줄었다는 점입니다. 누적합 문제를 풀다보면 누적합의 도착점 인덱스의 값에서 시작점 인덱스의 값을 빼면서 빠르게 값을 찾는 패턴이 자주 등장했습니다. 이 문제에도 같은 방식으로 접근하여 row를 기준으로 1차원 누적합을 구했는데 시간초과가 났습니다. 1. 이 문제는 2차원 누적합으로 접근해야합니다. 특정 좌표 x,y에서의 누적합은 0,0부터 x,y를 완전한 보드판으로 만들 때 몇 번 칠해야하는지의 횟수입니다.> 2차원 좌표 (x,y)의 누적합을 초기화 하는 방법은 sum(x,y) = ( 해당 인덱스에서 추가 할 값 ) - ( 그 외 영역의 값의 합) = ( 해당 인덱스에서 추가할 값) + s..

2026.03.11