취미로 코딩하기

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

이번에 볼 문제는 백준 3042번 문제인 트리플렛이다.
문제는 아래 링크를 확인하자.

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

칠판에 적힌 문자의 개수는 많아야 26개(대문자 알파벳의 가짓수)와 같음을 관찰하자. 그러므로 가능한 모든 "문자가 있는 세 칸을 고를 경우의 수"는 26가지 문자 중 3가지를 고르는 경우의 수인 2600가지이다.

경우의 수가 충분히 적으므로, 문자가 적힌 칸의 좌표들을 미리 전처리해둔 배열을 준비해두고 모든 위와 같은 경우에 대하여 세 지점이 일직선 위에 놓여있는지를 판별해 문제를 해결하자. 글쓴이는 이를 판별하기 위해 세 좌표를 A, B, C라 할 때 A와 B를 잇는 선분의 기울기와 B와 C를 잇는 선분의 기울기가 같은지를 확인하였다.

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

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int N;
string board[100];

int psize;
vector<pair<int, int>> points;
int ans;

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

	cin >> N;
	for (int r = 0; r < N; r++) cin >> board[r];

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c] != '.') points.emplace_back(make_pair(r, c));
		}
	}

	psize = points.size();
	for (int i = 0; i < psize; i++) {
		for (int j = i + 1; j < psize; j++) {
			int dx1 = points[j].first - points[i].first, dy1 = points[j].second - points[i].second;
			for (int k = j + 1; k < psize; k++) {
				int dx2 = points[k].first - points[j].first, dy2 = points[k].second - points[j].second;
				if (dx1 == 0 && dx2 == 0) ans++;
				else if (dx1 * dx2 && dy1 * dx2 == dx1 * dy2) ans++;
			}
		}
	}

	cout << ans;
}