문제 설명
변의 개수가 n개인 정다각형이 하나 주어지며, 이 다각형은 길이 n의 이진(binary) 문자열로 표현됩니다. 각 정점은 파란색(0) 또는 빨간색(1)으로 칠해져 있고, 색상 정보는 시계 방향 순서로 나열되어 있습니다. 이때 정다각형의 정점들만을 꼭짓점으로 사용하면서, 세 꼭짓점의 색이 모두 같은 이등변 삼각형의 개수를 구하는 것이 목표입니다.
예를 들어 입력이 polygon = "111010"이라면 결과는 2가 됩니다.
그림에서 확인할 수 있듯이 조건을 만족하는 삼각형은 ACE와 AFE, 총 두 개입니다.
풀이 접근 방법
이 문제는 “전체 이등변 삼각형의 수 − 꼭짓점 색이 섞인 이등변 삼각형의 수”를 계산하는 방식으로 해결합니다. 핵심 로직을 단계별로 정리하면 다음과 같습니다.
1단계. 전체 이등변 삼각형 개수 세기 — all() 함수
- n이 홀수이면 no = n × (n−1) / 2
- n이 짝수이면 no = n × (n/2 − 1)
- n이 3으로 나누어떨어지면 no에서 n/3 × 2를 차감합니다(정삼각형에 대한 중복 보정).
- no 값을 반환합니다.
2단계. 색이 섞인 이등변 삼각형 개수 세기 — non() 함수
non(a, n) 함수는 꼭짓점 색이 모두 같지 않은 이등변 삼각형의 수를 계산하며, n의 홀짝 여부에 따라 로직이 달라집니다.
n이 홀수인 경우
- s0, s1을 0으로 초기화한 뒤 문자열 a를 순회하며 '0'이면 s0를, 아니면 s1을 1씩 증가시킵니다.
- s = s0 × s1 × 6으로 설정합니다.
- n이 3으로 나누어떨어지면 n1 = n/3, n2 = n1 × 2로 두고, 모든 i에 대해 a[i] ≠ a[(i+n1) mod n]이면 s에서 2를 빼고, a[i] ≠ a[(i+n2) mod n]이면 역시 2를 뺍니다.
n이 짝수인 경우
- 짝수 인덱스와 홀수 인덱스를 분리해 네 개의 카운터(s00, s01, s10, s11)를 만듭니다. 인덱스 0부터 2씩 건너뛰며 '0'이면 s00, 아니면 s01을 증가시키고, 인덱스 1부터 2씩 건너뛰며 '0'이면 s10, 아니면 s11을 증가시킵니다.
- s에 s00 × s01 × 8, s10 × s11 × 8, s00 × s11 × 4, s10 × s01 × 4를 차례로 더합니다.
- n1 = n/2로 두고, a[i] ≠ a[(i+n1) mod n]인 모든 i에 대해 s에서 2를 뺍니다.
- n이 3으로 나누어떨어지면 홀수 경우와 동일한 방식으로 n/3, 2n/3 위치와 비교하여 보정합니다.
최종적으로 s / 2를 반환합니다.
3단계. 최종 답 계산
- n := 문자열 polygon의 길이
- no := all(n) − non(polygon, n) / 2
- no를 정수로 변환해 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
def all(n): if n % 2 == 1: no = n * (n - 1) / 2 else: no = n * (n / 2 - 1) if n % 3 == 0: no -= n / 3 * 2 return no def non(a, n): if n % 2 == 1: s0 = s1 = 0 i = 0 while i < n: if a[i] == '0': s0 += 1 else: s1 += 1 i += 1 s = s0 * s1 * 6 if n % 3 == 0: n1 = n / 3 n2 = n1 * 2 i = 0 while i < n: if a[i] != a[int((i + n1) % n)]: s -= 2 if a[i] != a[int((i + n2) % n)]: s -= 2 i += 1 else: s00 = s01 = s10 = s11 = s = 0 i = 0 while i < n: if a[i] == '0': s00 += 1 else: s01 += 1 i += 2 i = 1 while i < n: if a[i] == '0': s10 += 1 else: s11 += 1 i += 2 s += s00 * s01 * 8 s += s10 * s11 * 8 s += s00 * s11 * 4 s += s10 * s01 * 4 n1 = n / 2 i = 0 while i < n: if a[i] != a[int((i + n1) % n)]: s -= 2 i += 1 if n % 3 == 0: n1 = n / 3 n2 = n1 * 2 i = 0 while i < n: if a[i] != a[int((i + n1) % n)]: s -= 2 if a[i] != a[int((i + n2) % n)]: s -= 2 i += 1 return s / 2 def solve(polygon): n = len(polygon) no = all(n) - non(polygon, n) / 2 return int(no) polygon = "111010" print(solve(polygon))
실행 결과
입력:
polygon = "111010"
출력:
2
마무리
이 풀이는 전체 이등변 삼각형의 개수에서 색이 섞인 경우를 효율적으로 차감하는 방식으로, 반복문이 문자열을 한 번만 순회하므로 O(n) 시간 복잡도 안에 답을 구할 수 있습니다. 참고로 파이썬 3에서 나눗셈 연산자(/)는 실수를 반환하므로, 마지막에 int()로 감싸 정수 결과를 얻는 점도 눈여겨볼 필요가 있습니다. 정다각형 기하 문제에서 조합 계산과 색상 조건을 결합하는 대표적인 패턴이므로, 유사한 문제에 응용해 보기 좋은 예제입니다.