BOJ 3042 트리플렛

사용한 알고리즘

완전탐색

알고리즘 설명

크기는 커보이지만 알파펫은 하나씩만 사용되기 때문에 26 * 25 * 24 번만 비교하면 되기 때문에 모든 경우를 확인하기에 충분하다.
알파벳이 있는 좌표를 저장하고, 3개의 알파펫을 선택하고 기울기를 이용하여 3개의 알파펫으로 이루어지는 기울기가 같은지 확인한다.
같다면 결과에 추가한다.
직선판단을 CCW를 이용하여도 된다.

풀이

// baekjoon 3042 yechan
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> P;
const int MAX_N=101;

int N;
long long ret;
char board[MAX_N];
P alpha[27];
int alphaNum;

// (a.y - b.y)/(a.x - b.x) == (b.y - c.y)/(b.x - c.x)
// (a.y - b.y)(b.x - c.x) == (b.y - c.y)(a.x - b.x)

// 3좌표간의 기울기가 같은지 확인
inline bool check(P &a, P &b, P &c) {
    return ((a.second - b.second)*(b.first - c.first)) == ((b.second - c.second)*(a.first - b.first));
}

int main() {
    scanf("%d", &N);
    for (int i=0; i<N; i++) {
        scanf("%s", board);
        for (int j=0; j<N; j++) {
            if (board[j] == '.') continue;
            alpha[alphaNum] = {i,j};
            alphaNum++;
        }
    }

    for (int i=0; i<alphaNum; i++)
        for (int j=i+1; j<alphaNum; j++)
            for (int k=j+1; k<alphaNum; k++)
                    ret++;

    printf("%lld\n", ret);
    return 0;
}