C++로 N번 이동 후 삼각형 개수 구하는 방법

문제 소개

이 글에서는 먼저 색칠되지 않은 하나의 삼각형을 준비하고, 이 삼각형을 면적이 같은 네 개의 작은 정삼각형으로 나눕니다. 그런 다음 이 과정을 n번째 단계까지 반복한 뒤, 최종적으로 완성된 도형 안에 존재하는 정삼각형의 개수를 구하는 것이 목표입니다.

문제 해결 접근 방법

이 문제를 해결하는 방법은 크게 두 가지가 있습니다.

브루트 포스(Brute Force) 접근

삼각형의 개수가 매 단계마다 일정한 규칙, 즉 3 × 이전 개수 + 2만큼 증가한다는 사실을 관찰할 수 있습니다. 따라서 n번까지 반복문을 실행하면서 삼각형의 개수를 차례로 계산하면 됩니다.

예제 코드

#include <iostream>
using namespace std;
int main() {
   int n = 2; // 우리가 수행한 연산 횟수
   int count = 1; // 처음에는 삼각형이 하나뿐입니다
   for(int i = 0; i < n; i++) { // n번까지 반복
      count = 3 * count + 2; // 삼각형 개수가 3*이전개수+2씩 증가하므로
   }
   cout << count << "\n";
}

출력 결과

17

위 프로그램의 시간 복잡도는 O(N)입니다. 여기서 N은 수행한 연산 횟수를 의미합니다. 다만 더 큰 입력값을 다뤄야 하는 상황에서는 시간 복잡도를 한층 더 개선하는 것이 유용합니다.

효율적인 접근 방법

이 방법에서는 반복문 대신, 답을 바로 계산해 주는 수학 공식을 만들어 활용합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main() {
   int n = 2; // 우리가 수행한 이동 횟수
   int count;
   count = 2 * (pow(3, n)) - 1; // n번 이동 후 전체 삼각형의 개수
   cout << count << "\n";
}

출력 결과

17

위 코드의 시간 복잡도는 O(log N)으로, 여기서 N은 수행한 이동 횟수입니다.

코드 설명

위 프로그램에서는 주어진 과정을 해결하기 위한 공식을 세운 뒤, 필요한 값들을 공식에 대입하고 그 결과를 출력하는 방식으로 동작합니다. 덕분에 반복문 없이도 빠르게 정답을 구할 수 있습니다.

결론

이 글에서는 간단한 패턴 관찰과 수학적 공식을 활용하여 N번 이동 후 삼각형의 개수를 구하는 방법을 알아보았습니다. 또한 이 문제를 해결하는 C++ 프로그램과 함께 일반적인 방법(브루트 포스)과 효율적인 방법 두 가지 접근법을 모두 살펴보았습니다.

동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.