[ 백준 ] 10166 / 관중석

7102 단어 psbojboj

# Appreciation

/*
 * Problem :: 10166 / 관중석
 *
 * Kind :: Math
 *
 * Insight
 * - D=n 일 때, 4 번째 배치된 좌석을 (4,n) 이라고 하자
 *   + (2,3), (4,6), (6,9), ...
 *     위 수열에서 (2,3) 이 좌석으로 배치된 경우
 *     뒤의 (4,6), (6,9), ... 는
 *     (2,3) 에 의해 무대 중심이 가려져서 좌석으로 사용되지 못한다
 *     # 기약분수...?
 *       -> D1=a, D2=b 라면
 *          D1 부터 D2 까지를 분모로 하는
 *          서로다른 기약분수의 개수를 찾는 것이다!
 *
 * Point
 * - 중복을 알아서 처리해주는 Set 을 사용했더니
 *   시간초과가 났다
 *   + 좌석이 꽤 많은 듯 하다
 *     그래서 2차원 배열로 기약분수를 구현하고
 *     새로운 좌석을 발견할 때마다 개수를 증가시키는 방향으로 구현했다
 *
 * - D=3 일 때,
 *   0/3, 1/3, 2/3 으로도 볼 수 있지만
 *   1/3, 2/3, 3/3 으로도 볼 수 있다
 *   + 0/1, 0/2, 0/3, ... 의 경우 분모가 서로 달라져지지만
 *     1/1, 2/2, 3/3, ... 의 경우 모두 1/1 이 되어 간단하다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>
#include <numeric>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int D1, D2;
    cin >> D1 >> D2;

    // Process
    bool isSeat[D2+1][D2]; /* isSeat[j][i] = D=i 에서 j 번째 좌석이 유효하면 true
                            *                그 외 false */
    memset(isSeat, false, sizeof(isSeat));
    int ans = 0;
    for (int i=D1; i<=D2; i++) {
        for (int j=1; j<=i; j++) {
            /* 분모=i, 분자=j */
            int g = gcd(i, j);
            if (not(isSeat[j/g][i/g])) { /* 분모와 분자를 각각 최대공약수로 나누어
                                          * 기약분수를 만둘어줌 */
                isSeat[j/g][i/g] = true;
                ans++;
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */

좋은 웹페이지 즐겨찾기