345번째 문제 - 3042번 트리플렛

N*N 그리드에서 직선을 이루는 세 글자(트리플렛)의 개수를 구하는 문제다.

처음에 가로, 세로, 대각선만 생각해 몇번 오답을 받았지만 모든 기울기의 직선을 다 구해야한다.

그래서 모든 기울기에 대해 그리드를 순회하니 시간초과가 나왔다(n^5이니 .. 당연 ^^;;;)

그 다음 생각한 방법은 희소 행렬을 만들어 푸는 방법이다. vector<pair<int,int>>를 만들어서 세 점을 조합해 직선을 이루면 경우의 수에 추가하는 방법이다.  이런 방법으로 accept를 받았다.

#include <iostream>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

using namespace std;

int main()

{

int C,ans=0;

string t[101];

vector<pair<int,int>> v;

set<string> s;

cin>>C;

for(int i=0; i<C;i++)

{

cin>>t[i];

for(int j=0; j<C; j++)

{

if(t[i][j]!='.')v.push_back(pair<int,int>(i,j));

}

}

for(int i=0; i<v.size(); i++)

{

for(int j=i+1; j<v.size(); j++)

{

for(int k=j+1; k<v.size(); k++)

{

//

int y1=v[i].first;

int y2=v[j].first;

int y3=v[k].first;

int x1=v[i].second;

int x2=v[j].second;

int x3=v[k].second;

if(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)==0)

{

string tt ="";

tt+=t[y1][x1];

tt+=t[y2][x2];

tt+=t[y3][x3];

sort(tt.begin(), tt.end());

s.insert(tt);

}

}

}

}

cout<<s.size();

}

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이 문제에는 다음과 같은 조건이 있다. '한 알파벳을 여러 칸에 쓸 수는 없다.' 고로 프리플렛을 조합 했을때 중복이 나올 수 없다.  고로 set을 쓰는건 뻘짓이다. 그냥 직선 나왔을 때 갯수++만 해주자