문제 31
삼각형 칠하기
$H$개의 행과 $W$개의 열로 이루어진 격자가 있다.
처음에 모든 칸의 값은 $0$이다.
격자에 $N$개의 직각삼각형을 그린 뒤 각 칸의 값을 출력하라.
좌표 $(x, y)$는 왼쪽에서 $x$번째 열이면서 위에서 $y$번째 행인 칸을 나타낸다.
직각삼각형 $(x, y, k)$를 그리면 $0 \le d < k$인 모든 정수 $d$에 대해 $(x, y+d)$부터 $(x+d, y+d)$까지의 칸의 값이 $1$씩 증가한다.
입력
첫 번째 줄에 세 정수 $H$, $W$, $N$이 공백으로 구분되어 주어진다. $(1 \le H, W \le 1\,000; 0 \le N \le 100\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 세 정수 $x$, $y$, $k$가 공백으로 구분되어 주어진다. $(1 \le x \le W; 1 \le y \le H; 1 \le k; x+k-1 \le W; y+k-1 \le H)$
출력
$H$개의 줄에 걸쳐 각 줄에 $W$개의 정수를 공백으로 구분하여 출력한다.
예제 입력 1
5 6 2 1 1 3 3 2 3
예제 출력 1
1 0 0 0 0 0 1 1 1 0 0 0 1 1 2 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0
공식 해설
각 행의 시작과 끝을 따로 그리기
삼각형 $(x,y,k)$는 $y+d$행의 $x$열부터 $x+d$열까지를 칠한다. 이를 가로 차분으로 보면 $x$열에 $+1$, $x+d+1$열에 $-1$을 놓아야 한다. $(0\le d<k)$
$+1$의 위치들은 세로 선분을 이루고, $-1$의 위치들은 오른쪽 아래 대각선 선분을 이룬다. 따라서 이 두 선분을 서로 다른 차분 배열로 관리하면 된다.
행, 열 순서로 접근하는 두 배열 $V,D$를 $0$으로 초기화한다. 삼각형 하나마다
\[
V_{y,x}\mathrel{+}=1,\qquad V_{y+k,x}\mathrel{-}=1,
\]
\[
D_{y,x+1}\mathrel{-}=1,\qquad D_{y+k,x+k+1}\mathrel{+}=1
\]
을 기록한다.
세 방향의 누적으로 복원하기
먼저 $V$를 위에서 아래로 누적한다. 그러면 필요한 $k$개 행의 $x$열에만 $+1$이 생긴다. $D$는 왼쪽 위에서 오른쪽 아래로 누적한다. 즉 각 칸에 바로 왼쪽 위 칸의 값을 더한다. 그러면 같은 행들의 $x+d+1$열에만 $-1$이 생긴다.
마지막으로 각 행에서 $V+D$의 가로 누적합을 계산한다. $x$열에서 증가한 값이 $x+d+1$열에서 취소되므로 정확히 $x$열부터 $x+d$열까지 $1$이 남는다. 여러 삼각형도 표식을 모두 더한 뒤 같은 세 번의 누적을 수행하면 된다.
경계 밖의 종료 표식을 위해 행과 열에 여유 공간을 둔다. 삼각형당 갱신은 네 번이고 격자는 상수 번 순회하므로 시간복잡도는 $O(N+HW)$, 공간복잡도는 $O(HW)$이다.
구현 · 언어별 풀이
C++ 구현
두 차분 배열을 각각 $(H+2)\times(W+3)$ 크기로 잡아 아래·오른쪽 종료 표식을 저장한다. 대각선 누적은 행이 증가하는 순서로 수행하여 왼쪽 위 값이 먼저 완성되게 한다. 최종 가로 누적은 원래 $H\times W$ 범위만 출력한다.
C 구현
세로 경계와 대각 경계를 각각 int 차분 배열에 기록한다. 대각 배열은 오른쪽 경계 다음 칸까지 확보하고 행을 위에서 아래로 복원한다. 행 내부 누적값은 변수 하나로 처리해 세 번째 큰 배열을 만들지 않아도 된다.
Python 구현
두 차분 격자를 array('i')로 두면 각 칸의 Python 객체 비용을 줄인다. 세로 누적과 대각 누적을 이전 행에서 이어받은 다음 가로 누적한다. 양수·음수 표시를 함께 저장하므로 부호 있는 배열이 필요하다.
Java 구현
세로·대각 차분을 int[][] 또는 평탄 int[] 두 개에 둔다. 대각 경계용 여분 열을 확보하고, 행 복원 순서를 바꾸지 않는다. 덮인 횟수는 N 이하이므로 long 격자는 필요 없다.
Rust 구현
두 Vec<i32>에 세로·대각 차분을 기록한다. 행 y를 복원할 때 y-1의 세로 및 왼쪽 위 대각 값이 이미 계산되어 있어야 한다. 가로 누적은 행마다 0으로 다시 시작한다.
JavaScript 구현
세로 차분과 대각 차분은 각각 별도의 Int32Array로 평탄화한다. (h + 2) * (w + 2) 크기를 잡으면 삼각형의 아래쪽·오른쪽 종료 표식도 저장할 수 있다. 두 배열을 같은 객체로 공유하지 않는다.
위에서 아래로 행을 처리하며 세로 배열에는 바로 위 칸, 대각 배열에는 왼쪽 위 칸을 더한다. 그 행에서 두 값의 합을 왼쪽부터 누적해 출력한다. 차분 표식에는 음수가 들어가므로 unsigned 배열을 쓰지 않는다. 횟수는 $N$ 이하라 32비트 범위에 들어간다.