#문제

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

 

2740번: 행렬 곱셈

첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
 
int A[100][100];
int B[100][100];
 
int main(){
    int n, m, k;
    cin>>n>>m;
    // N*M 사이즈 행렬 A 입력 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>A[i][j];
        }
    }
    cin>>m>>k;
    // M*K 사이즈 행렬 B 입력 
    for(int i=0; i<m; i++){
        for(int j=0; j<k; j++){
            cin>>B[i][j];
        }
    }
    
    // 행렬곱셈의 결과는 N*K사이즈의 행렬. 
    for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            int c=0;
            for(int p=0; p<m; p++){
                c+=A[i][p]*B[p][j];
            }
            cout<<c<<' ';
        }
        cout<<"\n";
    }
    return 0;
}
 cs

##

o(n^3)의 알고리즘이라 행렬의 크기가 커지면 시간이 아주 오래 걸릴것같은데!

저작자표시 비영리 (새창열림)

'BOJ' 카테고리의 다른 글

BOJ 17298번 :: 오큰수  (0) 2019.12.26
BOJ 1874번 :: 스택 수열  (0) 2019.12.25
BOJ 11401번 :: 이항 계수 3  (0) 2019.12.25
BOJ 1920번 :: 수 찾기  (0) 2019.12.25
BOJ 2004번 :: 조합 0의 개수  (0) 2019.12.25

#문제

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

 

11401번: 이항 계수 3

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;
 
int mod = 1000000007;
 
long long int power(long long int a, long long int b){
    //a의 b제곱을 구하자
    long long result = 1;
    while( b>0 ){
        if( b%2 ){
            result  = (result*a)%mod;
        }
        
        a = (a*a)%mod;
        b/=2;
    }
    return result;
}
 
long long int comb(long long int n, long long int k){
    long long int facn = 1;
    long long int other = 1;
    
    // n!의 modulo 연산 결과 facn에 저장 
    for(long long int i=1; i<=n; i++){
        facn = (facn*i)%mod;
    }
    
    // k!의 modulo 연산 결과 other에 저장 
    for(long long int i=1; i<=k; i++){
        other = (other*i)%mod;
    }
    // (n-k)!의 modulo 연산 결과 other에 누적 저장. 
    for(long long int i=1; i<=n-k; i++){
        other = (other*i)%mod;
    }
    
    // n!*( k!(n-k)! )^mod-2의 modulo연산 결과 리턴. 
    return (facn*power(other, mod-2))%mod;
}
 
int main(){
    long long int n, k;
    cin>>n>>k;
    cout<<comb(n,k);
    return 0;
} 
 cs

##

단순히 n! / ( k! * (n-k)! ) 으로 계산하면

나눗셈에 대한 modulo 연산 분배법칙은 성립하지 않기 때문에,

( k! * (n-k)! )의 곱셈에 대한 역원을 이용해야 한다.   -> 페르마의 소정리 이용.

a(정수)와 p(소수)가 서로소일때 a^p % p = a가 성립한다.

a^p-1 % p = 1

a * a^p-2 % p = 1

=> a의 곱셈에 대한 역원은 a^p-2이다.

=> a^-1과 a^p-2의 modulo p 연산에 대한 결과가 같다.

 

=> ( n! * ( k! * (n-k)! )^-1 ) % p 와 ( n! * ( k! * (n-k)! )^p-2 ) % p  두 식의 결과가 동일하다.

나눗셈에 대한 modulo 연산을 곱셈으로 고쳐서 해결할 수 있다.

 

  • 단계별로 풀기 - 분할정복 카테고리에 있던 문제인데, 어떻게 분할정복해서 푸는것인지는 아직 이해 못했다......
저작자표시 비영리 (새창열림)

'BOJ' 카테고리의 다른 글

BOJ 1874번 :: 스택 수열  (0) 2019.12.25
BOJ 2740번 :: 행렬 곱셈  (0) 2019.12.25
BOJ 1920번 :: 수 찾기  (0) 2019.12.25
BOJ 2004번 :: 조합 0의 개수  (0) 2019.12.25
BOJ 1676번 :: 팩토리얼 0의 개수  (0) 2019.12.25

#문제

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

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
using namespace std;
 
void find(int *a, int start, int end, int value){
    int mid = (start+end)/2;
    
    // 범위 내에서 값을 찾을 수 없으면 start와 end가 역전됨 
    if( start > end ){
        cout<<"0\n";
        return;
    }
    // start <= end 
    else{
        // mid값보다 value가 크면 
        if( a[mid] < value ){
            find(a, mid+1, end, value);
        }
        // mid값보다 value가 작으면 
        else if( a[mid] > value ){
            find(a, start, mid-1, value);
        }
        // mid값과 value가 같으면 
        else{
            cout<<"1\n";
            return;
        }
    }
}
 
int main(){
    int n, m;
    cin>>n;
    int *a = new int[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
    
    cin>>m;
    int *nums = new int[m];
    for(int i=0; i<m; i++)
        cin>>nums[i];
        
    sort(a, a+n);
    
    //이분탐색으로 nums[i]의 값이 배열 a에 존재하는지 찾는다.
    for(int i=0; i<m; i++){
        find(a, 0, n-1, nums[i]);
    }
    return 0;
}
 cs

##

저작자표시 비영리 (새창열림)

'BOJ' 카테고리의 다른 글

BOJ 2740번 :: 행렬 곱셈  (0) 2019.12.25
BOJ 11401번 :: 이항 계수 3  (0) 2019.12.25
BOJ 2004번 :: 조합 0의 개수  (0) 2019.12.25
BOJ 1676번 :: 팩토리얼 0의 개수  (0) 2019.12.25
BOJ 1956번 :: 운동  (0) 2019.12.25

#문제

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

 

2004번: 조합 0의 개수

첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
 
int main(){
    int n, m;
    int two=0, five=0;
    // 입력 
    cin>>n>>m;
    // N!
    for(long long i=2; i<=n; i*=2)
        two += n/i;
    for(long long i=5; i<=n; i*=5)
        five += n/i;
 
    // M!
    for(long long i=2; i<=m; i*=2)
        two -= m/i;
    for(long long i=5; i<=m; i*=5)
        five -= m/i;
 
    // (N-M)!
    for(long long i=2; i<=n-m; i*=2)
        two -= (n-m)/i;
    for(long long i=5; i<=n-m; i*=5)
        five -= (n-m)/i;
    
    // 결과 출력 
    int result=min(two, five);
    cout<<result<<'\n';
    return 0;
}
 cs

##

nCm은 n! / ( m! * (n-m)! ) 이므로

n!에 포함된 2와 5의 개수 - m!에 포함된 2와 5의 개수 - (n-m)!에 포함된 2와 5의 개수 => min(2의 개수, 5의 개수) 가 nCm에 포함된 0의 개수이다.

 

n!에 i가 약수로 몇 개 들어있는가?

tmp = 2, ... , n으로 반복.

i개수 = i개수 + tmp/i;

i = i*i;

i<=n까지 반복한다.

 

ex) n=20일 경우, 2가 인수로 몇 개 들어있을까

i = 2          : 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 -> 10개

i = 4          : 4, 8, 12,16, 20                                 -> 5개

i = 8          : 8, 16                                                   -> 2개

i = 16        : 16                                                        -> 1개

총 18개 들어있다.

저작자표시 비영리 (새창열림)

'BOJ' 카테고리의 다른 글

BOJ 11401번 :: 이항 계수 3  (0) 2019.12.25
BOJ 1920번 :: 수 찾기  (0) 2019.12.25
BOJ 1676번 :: 팩토리얼 0의 개수  (0) 2019.12.25
BOJ 1956번 :: 운동  (0) 2019.12.25
BOJ 1629번 :: 곱셈  (0) 2019.12.24

#문제

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

 

1676번: 팩토리얼 0의 개수

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
 
int n;
int two, five=0;
 
int main(){
    cin>>n;
    
    // 2부터 시작해서 n까지의 수에 2와 5가 인수로 몇 개 존재하는지 센다 
    for(int i=2; i<=n; i++){
        int tmp=i;
        while( tmp%2==0 ){
            tmp = tmp/2;
            two++;
        }
        while( tmp%5==0 ){
            tmp = tmp/5;
            five++;
        }
    }
    
    // 2*5=10
    // 10은 2와 5의 개수 중 더 작은것만큼 만들 수 있다. 
    int result = min(two, five);
    cout<<result<<'\n';
    return 0;
}
 cs

##

N!은 1부터 N까지의 곱이다.

-> N!에서 0이 아닌 수가 나올 때까지 등장하는 0의 개수는 N!에 약수로 10이 몇 개 존재하는지 묻는 것이다.

-> 10은 2 * 5이므로 N!에 2와 5가 몇 개 들어있는지 센다.

-> 2부터 N까지의 수를 반복하여 2와 5로 얼마나 나누어떨어지는지 체크하고, 나누어떨어지면 2또는 5 중 해당하는 수의 개수를 하나 늘린다.

2와 5가 a, b개 존재한다면 만들 수 있는 10은 최대 min(a, b)개이다.

저작자표시 비영리 (새창열림)

'BOJ' 카테고리의 다른 글

BOJ 1920번 :: 수 찾기  (0) 2019.12.25
BOJ 2004번 :: 조합 0의 개수  (0) 2019.12.25
BOJ 1956번 :: 운동  (0) 2019.12.25
BOJ 1629번 :: 곱셈  (0) 2019.12.24
BOJ 1780번 :: 종이의 개수  (0) 2019.12.24

#문제

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

 

1956번: 운동

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2<=V<=400, 0<=E<=V*(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a->b임에 주의) 거리는 10,000 이하의 자연수이다.

www.acmicpc.net

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
#define INF 987654321
vector<pair<int, int> > city[401];
 
int main(){
    // 입력 
    int v, e;
    cin>>v>>e;
    for(int i=0; i<e; i++){
        int start, end, dist;
        cin>>start>>end>>dist;
        city[start].push_back(make_pair(end, dist));
    }
    
    /* 도로 길이의 합이 가장 작은 사이클을 찾고,
       최소 사이클의 도로 길이의 합을 출력
       운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력
    */
 
    // s[i][j]에는 i도시에서 j도시로 가는 최단거리 저장 
    int s[v+1][v+1];
    // s 배열을 모두 INF로 초기화. 
    for(int i=0; i<=v; i++)
        fill_n(s[i], v+1, INF);
    
    // 입력받은 도시 간 연결 도로를 s에 저장한다. 
    for(int i=1; i<=v; i++){
        for(int j=0; j<city[i].size(); j++){
            s[i][city[i][j].first] = city[i][j].second;
        }
    }
    
    // i 도시에서 출발해서 k도시를 거쳐 j도시로 가는 최단거리 계산 
    for(int k=1; k<=v; k++){        // 노드 k를 거쳐간다! 
        for(int i=1; i<=v; i++){
            for(int j=1; j<=v; j++){
                // i에서 출발해서 k를 거쳐 j로 도착한다.
                if( s[i][k]==INF || s[k][j]==INF ) continue;
                if( s[i][k] + s[k][j] < s[i][j] ){
                    s[i][j] = s[i][k] + s[k][j];
                 } 
            }
        }
    }
    
    // s[i][i]에는 i도시에서 출발해서 i도시로 도착하는 최단거리 저장.
    // s[i][i]를 0으로 초기화하지않고 INF로 초기화했으므로
    // 사이클이 형성되는 경우에만 i도시에서 출발해서
    // 돌아서 다시 i도시로 돌아오는 경우의 최단거리가 저장된다 
    int mincycle = 987654321;
    for(int i=1; i<=v; i++){
        mincycle = min( mincycle, s[i][i]);
    }
    
    // 도로 길이 합이 가장 작은 사이클의 도로 길이 합 mincycle 
    if( mincycle !=INF ){
        cout<<mincycle<<'\n';
    }
    else{
        cout<<-1<<'\n';
    }
    return 0; 
}
 cs

##

모든 정점에서 모든 정점까지의 최단거리를 구해야 출발 정점에서 출발정점으로 돌아오는 사이클의 최단거리를 구할 수 있으므로

플로이드 와샬(floyd Warshall)알고리즘을 사용했다.

저작자표시 비영리 (새창열림)

'BOJ' 카테고리의 다른 글

BOJ 2004번 :: 조합 0의 개수  (0) 2019.12.25
BOJ 1676번 :: 팩토리얼 0의 개수  (0) 2019.12.25
BOJ 1629번 :: 곱셈  (0) 2019.12.24
BOJ 1780번 :: 종이의 개수  (0) 2019.12.24
BOJ 1992번 :: 쿼드트리  (0) 2019.12.24

+ Recent posts

티스토리툴바