[ 백준 ] 10166 / 관중석
# 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 */
Author And Source
이 문제에 관하여([ 백준 ] 10166 / 관중석), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-10166-관중석
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* 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 이 되어 간단하다
*/
//
// 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 */
Author And Source
이 문제에 관하여([ 백준 ] 10166 / 관중석), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-10166-관중석저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)