BAEKJOON_code.plus 문제집/코딩테스트 준비 - 기초

코딩테스트 준비-기초: 수학

杉山空 2022. 2. 18. 15:42
728x90

10403번: 나머지

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

 

10430번: 나머지

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

www.acmicpc.net

그냥 문제에서 원하는걸 출력하자. 생각을 할 필요조차 없다.

1
2
3
4
5
6
7
#include <stdio.h>
int main(){
    int A,B,C;
    scanf("%d%d%d",&A,&B,&C);
    printf("%d\n%d\n%d\n%d",(A+B)%C,(A+B)%C,(A*B)%C,(A*B)%C);
    return 0;
}
cs

 

4373번: 1

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

 

4375번: 1

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

www.acmicpc.net

모든 자리수가 1인 수를 계속 만들어가며 n으로 나누어 떨어지는지 확인한다.

그 수가 k자리 수 라면 k를 출력하면 된다. (a mod c + b mod c)mod c=(a+b)mod c인 것을 이용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,i,ans;
    while(cin>>N){
        ans=i=1;
        while(ans%N){
            i++;
            ans=ans*10+1;
            ans%=N;
        }
        cout<<i<<endl;
    }
    return 0;
}
cs

1037번: 약수

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

 

1037번: 약수

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되

www.acmicpc.net

약수들을 오름차순 정렬하고 가운데에 있는 수를 곱하면 그 수가 된다. 약수의 개수가 홀수면 가운데에 있는 수의 제곱, 짝수면 가운데에 있는 두 수의 곱이다. 이것이 성립하는 이유는 초교 교육과정에서 다 배웠을것이다.

 

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
int N,a[53],i;
int main(){
    scanf("%d",&N);
    for(i=1;i<=N;i++)scanf("%d",&a[i]);
    std::sort(a+1,a+1+N);
    if(N%2)printf("%d",a[(N+1)/2]*a[(N+1)/2]);else printf("%d",a[N/2]*a[N/2+1]);
    return 0;
}
cs

 

17427번: 약수의 합 2

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

 

17427번: 약수의 합 2

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net

g(x)를 구할 때, x가 ⌊x/x개, (x-1)이 ⌊x/(x-1)⌋개... 1은 x개 이다.

이를 이대로 구현해주면 된다. 

1
2
3
4
5
6
7
8
#include<cstdio>
int main(){
    int N,i;long long ans=0;
    scanf("%d",&N);
    for(i=1;i<=N;i++)ans+=N/i*i;
    printf("%lld",ans);
    return 0;
}
cs

17425번: 약수의 합

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

 

17425번: 약수의 합

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net

위의 문제와 같은 문제다. 다면 미리 g(x)를 1000000까지 구해 두어야 한다.

이번에는 그냥 차례대로 i=1 부터 1000000까지 x가 i의 배수일때 g(x)값에 i를 더해주고, 이를 1~1000000 까지 누적해주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
long long g[1000003];
int main(){
    int T,N,i,j;
    for(i=1;i<=1000000;i++){
        for(j=1;i*j<=1000000;j++)g[i*j]+=i;
        g[i]+=g[i-1];
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        printf("%lld\n",g[N]);
    }
    return 0;
}
cs

 

2609번: 최대공약수와 최소공배수

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

 

2609번: 최대공약수와 최소공배수

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net

심플하게 노가다로 찾아준다. 두 수가 n, m일때 n*m/gcd(n,m)은 최소공배수이다.

이건 중학교 교육과정에서 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,i;
    scanf("%d%d",&n,&m);
    if(n>m)swap(n,m);
    i=n;
    while(m%i||n%i)i--;
    printf("%d\n%d",i,n*m/i);
    return 0;
}
cs

 

1978번: 소수 찾기

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

 

1978번: 소수 찾기

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

www.acmicpc.net

1000까지 모든 정수에 대해 소수인지 아닌지 먼저 확인해준 후 입력되는 정수에 대해 소수의 개수를 세준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
bool E[1003]={true,true};
int main(){
    int N,i,j,ans=0,q;
    for(i=1;i<=1000;i++){
        if(E[i])continue;
        for(j=i+i;j<=1000;j+=i)E[j]=true;
    }
    scanf("%d",&N);
    while(N--){
        scanf("%d",&q);
        if(!E[q])ans++;
    }
    printf("%d",ans);
    return 0;
}
cs

 

 

1929번: 소수 구하기

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

 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

1000000까지의 정수에대해 소수여부를 미리 판정해둔 후 그냥 M부터 N까지 소수를 출력하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
bool E[1000003]={true,true};
int main(){
    int N,M,i,j;
    for(i=1;i<=1000000;i++){
        if(E[i])continue;
        for(j=i+i;j<=1000000;j+=i)E[j]=true;
    }
    scanf("%d%d",&M,&N);
    for(i=M;i<=N;i++)if(!E[i])printf("%d\n",i);
    return 0;
}
cs

 

6588번: 골드바흐의 추측

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

 

6588번: 골드바흐의 추측

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰

www.acmicpc.net

이번에도 소수여부를 미리 판정하고 문제를 풀어준다. 작은 소수부터 n에서 빼서 그 수가 소수인지 확인한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
bool E[1000003]={true,true};
int main(){
    int n,i,j;
    for(i=1;i<=1000000;i++){
        if(E[i])continue;
        for(j=i+i;j<=1000000;j+=i)E[j]=true;
    }
    while(1){
        scanf("%d",&n);
        if(!n)break;
        bool stop=false;
        for(i=3;i<=n;i++){
            if(!E[n-i]&&!E[i]){
                printf("%d = %d + %d\n",n,i,n-i);
                stop=true;
                break;
            }
        }
        if(!stop)printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}
cs
728x90