BOJ [C++]) 10166번 관중석

https://www.acmicpc.net/problem/10166

10166번: 관중석

 

1. 문제

KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지름이 2인 원 위에는 좌석이 2개, 이런 식으로 반지름이 D 인 원 위에는 좌석이 D 개가 있다. 또한, 무대에서 정확히 북쪽 방향에는 모든 원들에 좌석이 있으며, 하나의 원 위에 있는 좌석들은 동일한 간격을 두고 배치되어 있다.

이번 공연에 반지름이 D1보다 같거나 크고, D2(D1 ≤ D2)보다 같거나 작은 원들에 배치된 좌석만을 활용하려고 한다. 단, 좌석을 점으로 간주했을 때, 다른 좌석에 의해 무대 중심이 가려지는 좌석은 사용하지 않고, 그렇지 않은 좌석은 모두 사용한다.

출처) 백준

위 그림은 D1 = 3, D2 = 6일 때, 배치된 좌석 및 좌석의 사용 여부를 나타낸다. 숫자는 원의 반지름을 나타내고, ●은 공연에 사용되는 좌석, ⊗은 공연에 사용되지 않는 좌석을 나타낸다. 

원의 반지름 D1과 D2를 입력으로 받아 사용되는 좌석의 수를 출력하는 프로그램을 작성하라.

 

 

2. PS.

- 최대공약수 규칙으로 중복을 제거하며 풀려고 했으나 .. 풀이가 너무 복잡해지고 오답이 나옴.

- 한 원안에 점이 일정한 간격으로 찍혀 있으므로 분수로 표현하기 좋아 double 변수를  사용함.

- 크기가 다른 각 원의 점 들을 모두 set container에 집어 넣어 중복을 제거 해줌.

#include <iostream>
#include <algorithm>
#include <deque>
#include <set>

using namespace std;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    double d1, d2;
    cin >> d1 >> d2;
    deque<double> v;
    set<double> s;
    for(double i = d1 ; i <= d2; i++) {
        v.push_back(i);
    }
    
    for(double i = 0; i < v.size(); i++) {
        for(double j = 1 ; j <= v[i]; j++) {
            s.insert(j/v[i]);
        }
    }
    
    cout << s.size();
    
}