백준 11320번 [삼각 무늬 - 1](C++) -yes6686- 티스토리

백준 문제 풀이: 11320 (삼각 무늬 - 1)

---

문제 링크: https://www.acmicpc.net/problem/11320

문제 설명:

주어진 두 정수 a와 b에 대해, 정사각형 한 변의 길이가 a / b인 삼각형 무늬의 총 개수를 계산하는 문제입니다. 삼각형 무늬는 홀수 개의 정사각형 블록으로 구성되며, 그 개수는 다음과 같은 공식에 따라 증가합니다: 1 + 3 + 5 + ... + (2n - 1), 여기서 n은 한 변의 길이입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

// 삼각 무늬의 총 개수를 계산하는 함수
int solve(int n) {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (2 * i - 1); // 홀수 값을 더해 누적
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T; // 테스트 케이스 개수 입력

    while (T--) {
        int a, b;
        cin >> a >> b; // 두 정수 a와 b 입력
        cout << solve(a / b) << '\n'; // 한 변의 길이: a / b
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 한 변의 길이 n에 대해 삼각형 무늬의 총 개수를 계산합니다. 삼각형의 무늬는 1부터 시작해 2n - 1까지의 홀수를 누적 합하는 형태입니다.
• 구현 세부사항:
  • 한 변의 길이 n는 a / b로 계산됩니다.
  • solve() 함수: 1부터 2n - 1까지의 모든 홀수를 더해 총 개수를 반환합니다.
• 시간 복잡도 분석:
  • 각 테스트 케이스에서 solve() 함수는 O(n) 시간 복잡도로 실행됩니다.
  • 입력 개수를 T라고 하면, 전체 시간 복잡도는 O(T ⋅ n)입니다.

---

결과

주어진 입력에 대해 삼각 무늬의 총 개수를 정확히 계산하고 출력합니다.

• 입력 예시:

  2  
  3 1  
  6 2

• 출력 예시:

  9  
  9

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!