[백준 / BOJ] 3042 트리플렛

문제

출처 : www.acmicpc.net/problem/3042

3042번: 트리플렛

N*N그리드가 주어지고, 각 칸에 알파벳 혹은 '.'이 주어진다. 이때 3개의 알파벳이 한 직선을 이루면 이를 트리플렛 이라고 한다.

예를들어, 

...A
..B.

.C..

D...

은

ABC가 하나의 트리플렛을 이룬다, BCD가 트리플렛을 이룬다... 라고 생각하면된다.

 

풀이

그냥 완전탐색을 할경우,

N이 최대 100이고 N*N이므로, 칸의 총 갯수는 100*100 = 10000개이다. 여기서 3개의 수를 뽑는경우의수는 (10000)C(3)이 되서, 시간초과가 난다. 

 

트리플렛을 이룬다는건 알파벳 3개가 모두 한 직선에 있다는뜻이다. 즉, 3개의 기울기가 같다고 생각하면된다.

따라서 알파벳을 기준으로 완전탐색을 할건데, 알파벳은 중복이 안되므로, 총 26개가 나올수있고, 이중 3개를 뽑는 경우의수 이므로 (26)C(3)이 된다. 

3중반복문을 돌리면서,

이 3개의 수의 기울기가 같다면 트리플렛을 이룬다고생각하고 cnt++을 해주면 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/3042%20%ED%8A%B8%EB%A6%AC%ED%94%8C%EB%A0%9B/main.cpp

devxb/JJUNalgo