프로그래밍

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

[난이도] Gold5
[유형] 수학

[풀이]
1과 2가 무조건 동시에 사용되어야 하므로, 전체 수열의 합이 3의 배수여야 하고
(전체 수열의 합 / 3) = (물뿌리개를 사용해야 하는 횟수) = (2를 사용해야 하는 횟수) 이므로
1~N 사과나무들의 2로 나눈 몫의 합이 위의 (2를 사용해야 하는 횟수) 이상이어야 합니다.

이것을 만족하지 못하는 조건은 다음과 같이 표현이 가능합니다.
cnt : 2로 나눈 몫의 합
if(sum%3||cnt<sum/3) {
    puts("NO");
    return 0;
}

#include <cstdio>
int N,a[100000],sum,cnt;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&a[i]);
        sum+=a[i];
        cnt+=a[i]/2;
    }
    if(sum%3||cnt<sum/3) {
        puts("NO");
        return 0;
    }
    puts("YES");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/19539.cpp

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

[난이도] Silver1
[유형] 수학

[풀이]
1의 개수끼리 최대 공약수를 구한 뒤,
이 수만큼 1을 출력해주면 정답이라고 합니다.
증명은 못하겠어서 gcd 구하는 연습용으로 풀었습니다..

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
ll a,b;
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    while(b!=0){
        ll c = a%b;
        a=b;
        b=c;
    }
    return a;
}
int main(){
    scanf("%lld%lld",&a,&b);
    for(int i=0;i<gcd(a,b);i++) printf("1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1850.cpp

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

[난이도] Bronze2
[유형] 수학

[풀이]
s가 1이 나올때마다 방향을 반대로 바꿔주고,
회전수는 1로 시작해서 b/a를 계속 곱해주면 됩니다. 정수인 답이 나온다는 조건이 있기 때문에
회전수는 계속 정수로 유지될 것이기 때문에 계속 나눠주어도 됩니다.

#include <cstdio>
int M,d,cur=1;
int main(){
    scanf("%d",&M);
    while(M--){
        int a,b,s;
        scanf("%d%d%d",&a,&b,&s);
        if(s==1) d=1-d;
        cur=cur*(double)b/a;
    }
    printf("%d %d",d,cur);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Bronze2/10834.cpp

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

[난이도] Bronze3
[유형] 수학

[풀이]
각 학교에서 사솨개수%학생수 만큼 사과가 남습니다.

#include <cstdio>
int N,a,b,ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d%d",&a,&b);
        ans+=b%a;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Bronze3/10833.cpp

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

[난이도] Silver3
[유형] 수학

[풀이]
double형으로 입력을 받고 문제의 조건대로 평균들을 구해주면 됩니다.
반올림 처리가 중요한데.
a라는 숫자를 소숫점 3번째에서 반볼림을 하려면
floor(a*100+0.5)/100 와 같이 floor 함수를 이용해주면 됩니다.

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int N,K;
double a[100001];
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++) scanf("%lf",&a[i]);
    sort(a+1,a+N+1);
    double sum=0;
    for(int i=K+1;i<=N-K;i++){
        sum+=a[i];
    }
    double t = sum / (N-2*K);
    printf("%.2lf\n",floor(t*100+0.5)/100);
    for(int i=1;i<=K;i++){
        a[i]=a[K+1];
        a[N-i+1] = a[N-K];
    }
    sum=0;
    for(int i=1;i<=N;i++) sum+=a[i];
    t = sum / N;
    printf("%.2lf",floor(t*100+0.5)/100);    
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/6986.cpp

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

[난이도] Silver5
[유형] 수학

[풀이]
가장 큰 변이 나머지 두 변의 합보다 작으면 삼각형을 무조건 만들 수 있습니다.

#include <cstdio>
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        for(int j=i;j<N;j++){
            int k=N-i-j;
            if(j>k) break;
            if(i+j>k) ans++;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver5/2622.cpp

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

[난이도] Bronze1
[유형] 수학

[풀이]
N,M,k,D가 모두 주어지고 A=k*B 이기 때문에 식을 잘 세워보면
미지수는 B밖에 남지 않는 다는 것을 알 수 있습니다.
식을 잘 정리한 뒤 반복문을 이용해 B가 조건을 만족하지 않을 때까지 증가시켜가며 B의 최적값을 찾아주면 됩니다.

#include <algorithm>
using namespace std;
using ll = long long;
int T;
ll N,M,k,D;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld%lld",&N,&M,&k,&D);
        ll B=0;
        while(N*M*B*(k*(M-1)+M*(N-1))<=2*D) B++;
        if(B<=1) {
            puts("-1");
            continue;
        }
        ll a=N*M*(B-1)*(k*(M-1)+M*(N-1));
        printf("%lld\n",a/2);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Bronze1/21760.cpp

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

[난이도] Gold5
[유형] 수학

[풀이]
1~1000000의 수에 대해 각각의 모든 약수를 구해서 미리 저장해놔야 하는데
일반적으로 루트N에 모든 약수를 구하는 방법으로
각각의 수에 대해 구할 경우 O(루트(1000000))의 복잡도가 필요합니다.
위 방법을 사용할 경우 O(1000000*1000) 의 시간이 걸리므로 시간내에 해결이 불가능합니다.
에라토스테네스의 체를 이용해 소수를 구할때와 비슷한 방식으로
f[1000001] 배열을 미리 선언해놓고 1~1000000까지를 순회하면서
i에 대해 f[i*1],f[i*2],f[i*3].. (i*k <=1000000) 에 i를 더해주면 f 배열을 채울 수 있습니다.
이를 이용해 부분합 배열 s를 만들어 채워주면 쿼리에 대한 답을 O(1)에 구할 수 있습니다.

#include <cstdio>
using ll = long long;
int T,f[1000001];
ll s[1000001];
int main(){
    scanf("%d",&T);
    for(int i=1;i<=1e6;i++)
        for(int j=i;j<=1e6;j+=i) f[j]+=i;
    for(int i=1;i<=1e6;i++) s[i]=f[i]+s[i-1]; 
    while(T--){
        int v;
        scanf("%d",&v);
        printf("%lld\n",s[v]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17425.cpp