[백준 23823] 초코칩케이크 [Java]

문제

http://boj.ma/23823

23823번: 초코칩 케이크

 

요약

• 한 행/열의 모든 조각에 초코칩을 1개씩 올릴 때, 초코칩이 가장 많이 있는 조각의 수를 구하자.
• $n ≤ 3e4, q ≤ 1e5$

---

풀이 과정

아이디어

케이크의 모든 조각에 초코칩을 올리는 갱신 과정 $O(nq)$이므로 시간 초과가 발생한다.

임의의 칸(i, j)에 있는 초코칩 개수는

• R[i] : i 번째 가로 줄에 초코칩을 올린 횟수
• C[j] : j 번째 세로 줄에 초코칩을 올린 횟수

의 합으로 표현할 수 있다.

따라서 초코칩이 가장 많이 놓인 조각의 수는 R[i]와 C[j]가 최대인 교차점이 된다.

각 쿼리마다 R[i] + C[j] = maxRow + maxCol를 만족하는 칸의 수를 구하면 되며, 이는 maxRow인 행의 수 * maxCol인 열의 수로 나타낼 수 있다.

만약 행 또는 열 쿼리가 없을 수 있으므로, maxRowCount, maxColCount는 N으로 초기화해 동일한 식으로 처리하자.

int[] R = new int[N + 1], C = new int[N + 1];
int maxRow = 0, maxCol = 0;
int maxRowCount = N, maxColCount = N;

1. R[a]에 초코칩을 올리는 횟수를 증가시키고,
2. R[a]가 초코칩이 최대로 올라간 조각(maxRow)와 수가 동일하다면 교차점(maxRowCount)을 증가시켜주자.
3. 만약 R[a]가 기존에 초코칩이 최대로 올라간 조각보다 더 많이 올라갔다면, 새로운 교차점이 형성되야 한다.

// Solve
if (t == 1) {
	++R[a];
	if (R[a] == maxRow) {
		++maxRowCount;
	} else if (R[a] > maxRow) {
		maxRowCount = 1;
		maxRow = R[a];
	}
} else {
	/* 행과 열에 대한 로직은 동일하다. */
}

성능 분석

• 시간 복잡도: $O(Q)$
• 제출결과: Accepted / 488ms / 23,823KB

---

회고

행과 열을 직접 갱신하지 않고, 상태를 축약해 표현하는 방식은 구현보다는 과정을 이해하고 표현하는 개념적 과정이 어려웠다.

이로 인해 변수명이 의도를 정확히 전달하는지에 대해 많은 고민을 하게 되었고, 그 과정에서 전체 로직을 다시 점검하며 논리적 문제를 사전에 제거하는 습관의 중요성을 다시 한 번 느끼게 되었다.

---

참고

문제

http://boj.ma/23823

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/23823.java