취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 8907번 문제인 네온 사인이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/8907 

처음에는 주어진 그래프의 인접행렬(adjacency matrix)를 만들어 세제곱하는 것으로 길이3의 사이클의 개수를 세는 풀이를 구상하였다. O(N^3)이지만 출제자가 적절히 테스트케이스의 수(T의 값)를 융통성 있게 만들어서 통과가 가능하기를 바라고 제출해보았지만 시간초과를 받았다.

더 좋은 방법으로 삼각형을 계수해보자.

모든 "단색이 아닌" 삼각형은 빨간색과 파란색 변으로 이루어진 각을 2개씩 갖고, "단색인" 삼각형은 그러한 각을 갖지 않는다는 점을 이용하면 "단색이 아닌" 삼각형의 개수를 셀 수 있다. 따라서, 전체 삼각형의 개수에서 "단색이 아닌" 삼각형의 개수를 빼는 것으로 문제의 답안을 구할 수 있다.

N=1000인 경우에 나올 수 있는 전체 삼각형의 개수를 32비트 정수의 범위 내로 나타낼 수 있으므로, 오버플로우의 위험에 대한 걱정 없이 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int red[1000];
int blue[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		memset(red, 0, sizeof(red));
		memset(blue, 0, sizeof(blue));

		int N; cin >> N;
		for (int r = 0; r < N; r++) {
			for (int c = r + 1; c < N; c++) {
				int x; cin >> x;
				if (x) {
					red[r]++; red[c]++;
				}
				else {
					blue[r]++; blue[c]++;
				}
			}
		}

		int cnt = 0;
		for (int i = 0; i < N; i++) cnt += red[i] * blue[i];
		cout << N * (N - 1) * (N - 2) / 6 - (cnt / 2) << '\n';
	}
}