8457 알 덴테 스파게티

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWzal4EKksEDFAVU&categoryId=AWzal4EKksEDFAVU&categoryType=CODE

SW Expert Academy

 

#include <stdio.h>
 
number_of_sandglass(int N, int B, int E);
 
int main(void) {
    int test_case, count;
 
    scanf("%d", &test_case);\
 
    for (count = 1;count <= test_case;count++) {
        int n, b, e, result;
        scanf("%d %d %d", &n, &b, &e);
        printf("#%d %d\n", count, number_of_sandglass(n, b, e));
    }
 
    return 0;
}
 
 
int number_of_sandglass(int N, int B, int E) {
    int under = B - E;
    int upper = B + E;
    int i, a[100], temp, num;
    for (i = 0;i < N;i++)
        scanf("%d", &a[i]);
    for (i = 0, num = 0; i < N; i++) {
        temp = B / a[i];
        if (temp == 0) {
            if (a[i] <= upper && a[i] >= under) num++;
            } // B / a[i]의 값이 0인 경우 (B < xi인 경우) 모래시계를 한 번 뒤집었을 때 범위 내의 시간을 측정할 수 있는지 확인
        else if ((B - a[i] * temp) <= a[i] * (temp + 1) - B) {
            if ((temp * a[i]) <= upper && (temp * a[i]) >= under) num++;
            } // temp일 때 temp + 1일 때보다 B에 근접하는 경우 모래시계를 temp번 뒤집었을 때 범위 내의 시간을 측정할 수 있는지 확인.
        else {
            if (a[i] * (temp + 1) <= upper && a[i] * (temp + 1) >= under) num++;
        } // temp + 1일 때 temp일 때보다 B에 근접하는 경우 모래시계를 (temp + 1)번 뒤집었을 때 범위 내의 시간을 측정할 수 있는지 확인.
    }
    return num;
}
 

스파게티 그까짓 거 좀 대충 먹으면 안 되나... 암튼

 

한 마디로 특정 범위 내에 xi의 배수가 존재하는지를 확인해야 하는 문제이다.

그러기 위해서는 xi의 배수 중에서 면이 가장 이상적으로 익는 B초에 가장 근접하는 수를 찾아야 한다.

처음에는 그냥 B / xi의 값을 xi에 곱했을 때 나오는 수가 B에 가장 근접한 수일 거라고 생각했는데, 이렇게 하면 B보다 큰 수 중에서 B에 근접하는 수는 고려되지 않는다는 것을 알았다.

예를 들어 B가 100이라고 하고 xi가 17이라고 했을 때 100 / 17 = 5이고, 17 * 5 = 85이므로 17의 배수 중에서 100에 가장 가까운 수는 85라고 생각할 수 있지만 17 * 6 = 102이므로 17에 6을 곱하면 5를 곱했을 때보다 더 100에 가깝다. 만약 E가 4라면 허용되는 범위가 96이상 104 이다. 전자만 봤을 때는 17초의 모래시계는 이 범위에 포함되지 않지만, 후자까지 생각해 보면 포함이 되는 것이다.

이와 같은 문제가 발생하는 이유는 나머지 때문이다. '/' 연산을 사용하면 나머지는 고려되지 않으니까..... 100을 17로 나누면 나머지가 15가 되므로 85는 100보다 15만큼 작다. 반면 102는 100과 2 차이가 나므로 100보다 2만큼밖에 크지 않다. 그래서

1. B보다 작은 수 중에서 B와 가장 근접한 수 (B / xi * xi)

2. B보다 큰 수 중에서 B와 가장 근접한 수((B / xi + 1) * xi )

1, 2번 중에서 B와 더 가까운 수를 찾을 수 있도록 수정하였다. B와의 차를 구해서 차가 더 작은 쪽이 B와 더 가까울 것.

이렇게 해서 구해진 B와 가장 가까운 수가 범위 내에 있다면 개수를 1 증가시키면 된다.

 

여기서 내가 또 간과한 것이 있는데, B / xi가 0일 때이다. xi가 B보다 크면 B를 xi로 나누었을 때 몫이 0이 된다. 나는 xi가 B보다 크다면 당연히 범위에서 벗어날 것이라고 막연하게 생각해서 B / xi일 때는 continue를 사용해 넘어가도록 코드를 작성했었다. 그런데 xi가 B보다 크더라도 xi에 1을 곱했을 때의 값이 허용 범위 안에 들어간다면 이또한 사도 되는 모래시계이므로... 이 경우 또한 고려되도록 수정해주었다.