본문 바로가기
알고리즘/SWEA

[SWEA] 8457. 알 덴테 스파게티

by hyerann 2020. 2. 17.

문제 이해만 잘하면 아주 간단하게 해결할 수 있는 문제이다.

모래시계 단위로 B-E~B+E를 나눴을 때 나머지가 0인 경우가 하나라도 있으면 구입해도 되는 모래시계이다.

 

B-E를 모래시계 단위로 나눴을 때, 

나눠 떨어진다면 B-E를 측정할 수 있으므로 구입해도 되는 모래시계

나눠 떨어지지 않는다면 B-E에서 (B-E를 모래시계 단위로 나눈 나머지)를 뺀 시간만큼은 측정할 수 있음

→ 모래시계 단위를 한번 더 더했을 때 B+E 이하라면 구입해도 되는 모래시계

#include <iostream>

using namespace std;

int N, B, E;
int sandglass[100];

int getResult() {
    int result = 0;
    
    for(int i=0; i<N; i++) {
        //B-E~B+E 중에 나눠 떨어지는게 있으면 된다.
        int rest = (B-E)%sandglass[i];
        if(rest == 0) {
            result++;
            continue;
        }
        if(B-E-rest+sandglass[i] <= B+E) {
            result++;
        }
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T;
    cin >> T;
    
    for(int tc=1; tc<=T; tc++) {
        cin >> N >> B >> E;
        for(int i=0; i<N; i++) {
            cin >> sandglass[i];
        }
        cout << '#' << tc << ' ' << getResult() << '\n';
    }
    
    return 0;
}

 

댓글