백준 4030번 [포켓볼](C++) -yes6686- 티스토리

백준 문제 풀이: 4030 [포켓볼]

---

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

문제 설명:

1부터 특정 자연수까지의 제곱수 중, 하나 적은 값이 삼각수인 수를 찾아 해당 범위 내 개수를 출력하는 문제입니다.

삼각수는 아래와 같이 정의됩니다:

T(n) = n * (n + 1) / 2

주어진 두 수 (a, b)에 대해 a < x+1 < b를 만족하는 수 중 조건에 맞는 값을 찾습니다. 입력이 0, 0일 때 종료합니다.

---

문제 해결 코드

#include <iostream>
#include <map>
#include <cmath>
#define INF 1000000000
using namespace std;

int cnt4[100001];
map<int, int> mp3;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int s = 1;

    // 삼각수를 미리 계산하여 map에 저장
    while (true) {
        long long int ss = (s * (s + 1)) / 2;
        if (ss > INF) {
            break;
        }
        mp3[ss] = 1;
        s++;
    }

    // 제곱수 중 하나 적은 값이 삼각수인 것을 카운트
    s = 1;
    while (true) {
        long long int ss = s * s;
        if (ss > INF) {
            break;
        }
        if (mp3[ss - 1] == 1) {
            cnt4[s] = cnt4[s - 1] + 1;
        } else {
            cnt4[s] = cnt4[s - 1];
        }
        s++;
    }

    // 각 입력 범위에 대한 결과 계산 및 출력
    int t = 1;
    while (true) {
        int a, b;
        cin >> a >> b;
        if (a == 0 && b == 0) break;
        
        int cnt = cnt4[(int)sqrt(b - 1)] - cnt4[(int)sqrt(a)];
        cout << "Case " << t++ << ": " << cnt << '\n';
    }
    return 0;
}

예제

입력:
1 10
11 20
0 0

출력:
Case 1: 1
Case 2: 1

---

코드 설명

• 삼각수 계산: 삼각수를 미리 계산해 map에 저장하여 빠르게 조회할 수 있도록 합니다.
• 제곱수 확인: 제곱수 중 하나 적은 값이 삼각수인지 확인하며 누적 카운트를 저장합니다.
• 입력 범위 처리: 입력된 각 범위에서 시작값과 끝값의 누적 카운트를 차감하여 조건에 맞는 수의 개수를 구합니다.

시간 복잡도

• 삼각수 및 제곱수 계산: O(N)
• 범위 내 조건 확인 및 출력: O(T), T는 입력 개수

---

결과

이 코드는 효율적으로 삼각수 및 제곱수의 관계를 계산하고, 입력 범위에 따라 조건을 만족하는 수를 빠르게 계산합니다. 최적화를 위한 다른 접근 방식이나 피드백은 언제든지 환영합니다!