10166번 관중석

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

복습, 문제, 공부

처음에는 어떤 수 x에 대하여 d1 <= 2x <= d2라면,

x는 아예 없애고, 2x - x = x를 세주는 방식으로 했다.

예를 들면, d1 = 3, d2 = 6이라면

3 4 5 6 일 것이고,

3의 정확히 2배인 6이 존재하므로, 3은 세주지 않고, 6 - 3 = 3을 세준다.

즉, 0 4 5 3 → 0 + 4 + 5 + 3 = 12라고 생각했었다.

하지만 이런 문제가 아니었다.

3 4 5 6 에서 6을 봐보자.

6의 공약수들을 보면, 1, 2, 3, 6일 것이다.

이 공약수들은 6하고 위치가 겹칠 것이다.

이러한 것을 활용해야 하는 문제이다.

그리고 중복해서 셈을 해서는 안 되므로

(예시 : i = 8, j = 4이고, i = 4, j = 2일 때, 겹침에도 불구하고 그대로 또 셀 수도 있다.)

2차원 배열로 방문 처리를 한다.

이 때, 최대공약수를 분모로 하여, i와 j를 각각 나누어 준다.

그러면 해당 i에 대하여 i까지 방문 처리를 하게 되고,

i보다 더 큰 숫자 k에 대하여, k는 i까지 방문 처리를 했으니, 세지 않아도 된다.

(사실 조금 헷갈림)

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 2002
 
int d1, d2, ans;
bool use[Max][Max];
 
int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a%b);
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &d1, &d2);
    
    for (int i = d1; i <= d2; i++) {
        for (int j = 1; j <= i; j++) {
 
            // 최대 공약수
            int m = gcd(i, j);
 
            if (!use[i / m][j / m]) {
                use[i / m][j / m] = true;
                ++ans;
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}