#문제

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

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,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
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
 
// 행렬의 사이즈 
int n;
// 1<= b <= 100,000,000,000 
long long int b;
 
// 단위행렬
vector<vector<int> > one(5, vector<int>(5)); 
 
vector<vector<int> > matmul(vector<vector<int> > a, vector<vector<int> > b){
    int size = a.size();
    
    vector<vector<int> > result(size, vector<int>(size));
    
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            for(int k=0; k<size; k++){
                result[i][j]+=(a[i][k]*b[k][j])%1000;
            }
            result[i][j]%=1000;
        }
    }
    return result;
}
 
vector<vector<int> > matpow(vector<vector<int> > a, long long int b){
    if( b==0 ){
        return one;
    }
    else if( b==1 ){
        return a;
    }
    else if( b%2==0 ){
        vector<vector<int> > tmp = matpow(a, b/2);
        return matmul(tmp, tmp);
    }
    else{
        vector<vector<int> > tmp = matpow(a, b-1);
        return matmul(a, tmp);
    }
}
 
void printmat(vector<vector<int> > v){
    int size = v.size();
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            printf("%d ", v[i][j]%1000);
        }
        printf("\n");
    }
}
 
int main(){
    scanf("%d %lld", &n, &b);
    // n*n사이즈 행렬 입력 
    vector<vector<int> > mat(n, vector<int>(n));
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &mat[i][j]);
        }
        one[i][i]=1;
    }
    
    vector<vector<int> > answer(n, vector<int>(n));
    answer = matpow(mat, b);
    
    printmat(answer);
    return 0; 
} 
 cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1654번 :: 랜선 자르기  (0) 2019.12.28
BOJ 2049번 :: 피보나치 수 3  (0) 2019.12.28
BOJ 10816번 :: 숫자 카드 2  (0) 2019.12.27
BOJ 1966번 :: 프린터 큐  (0) 2019.12.27
BOJ 11866번 :: 조세퍼스 문제 0  (0) 2019.12.26

#문제

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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m;
vector<pair<int, int> > card;
 
int bsearch(int x){
    int start = 0;
    int end = card.size();
    int mid;
    while( start <= end ){
        mid = (start+end)/2;
        if( card[mid].first < x){
            start = mid+1;
        }
        else if( card[mid].first > x){
            end = mid-1;
        }
        else{
            // card[mid].first==x
            return card[mid].second; 
        }
    }
    // x가 쓰여진 카드를 찾을 수 없을때
    return 0; 
}
 
int main(){
    scanf("%d", &n);
    vector<int> nums;
    for(int num=0; num<n; num++){
        int x;
        scanf("%d", &x);
        nums.push_back(x);
    }
    // 가지고있는 카드들 카드에 적힌 수 기준으로 오름차순정렬 
    sort(nums.begin(), nums.end());
    
    // 입력받은 카드들 다시 벡터에 넣으면서 개수 저장. 
    card.push_back(make_pair(nums[0],1));
    int index =0;
    for(int i=1; i<n; i++){
        if( nums[i]==card[index].first){
            card[index].second++;
        }
        else{
            card.push_back(make_pair(nums[i], 1));
            index++;
        }
    }
    scanf("%d", &m);
    for(int i=0; i<m; i++){
        int x;
        scanf("%d", &x);
        printf("%d ", bsearch(x));
    } 
    return 0; 
} 
 cs

##

처음에 n개의 카드에 적힌 숫자들을 입력받으면서

vector<pair<int, int> > 를 사이즈만큼 순회하면서 같은 숫자가 적힌 카드가 있다면 카드 개수를 1 늘리고, 그런 카드가 없다면 {카드에 적힌 숫자, 1}을 push하는 방식으로 코드를 작성했는데, 시간초과가 발생했다.

 

중복에 관계없이 입력받는 카드에 적힌 수를 모두 vector 에 push하고, 그 벡터를 정렬한 후에 vector<pair<int, int> >에 저장하면서 카드 숫자를 저장하니 시간초과를 해결할 수 있었다.

 

 

이 문제를 푼 다른 분들의 풀이를 보니, lower_bound와 upper_bound를 이용한 풀이들이 많았다.

lower_bound함수는 lower_bound(arr, arr+n, num); 와 같이 사용하고, arr ~ arr+n 까지에서 num 이상의 숫자를 찾는다면 그 위치의 iterator를 반환.

upper_bound함수도 upper_bound(arr, arr+n, num); 과 같이 사용하고, arr ~ arr+n까지에서 처음으로 num을 초과하는 숫자를 찾으면 그 위치의 iterator를 반환한다.

 

-> 위의 문제에 적용하려면, x가 적힌 카드의 개수가 몇 개인지 찾고싶을때

upper_bound(nums.begin(), nums.end(), x) - lower_bound(nums.begin(), nums.end(), x) 가 x가 적힌 카드의 개수가 된다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2049번 :: 피보나치 수 3  (0) 2019.12.28
BOJ 10830번 :: 행렬 제곱  (0) 2019.12.27
BOJ 1966번 :: 프린터 큐  (0) 2019.12.27
BOJ 11866번 :: 조세퍼스 문제 0  (0) 2019.12.26
BOJ 17298번 :: 오큰수  (0) 2019.12.26

#문제

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

 

1966번: 프린터 큐

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를

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 <queue> 
using namespace std;
 
int tc, m, n; 
 
int main(){
    cin>>tc;
    for(int t=0; t<tc; t++){
        cin>>n>>m;
        // 문서의 중요도 큰것부터 나오도록 저장.
        priority_queue<int> pq; 
        // 문서 번호, 중요도 저장. 
        queue<pair<int, int> > q;
        
        // n개 문서의 중요도를 순서대로 입력. 
        for(int d=0; d<n; d++){
            int priority;
            cin>>priority;
            q.push(make_pair(d, priority));
            pq.push(priority);
        }
        int printnum=0;
        
        // m 문서가 몇 번째에 출력될지 찾자.
        while(!q.empty()){
            // 현재 큐의 맨 앞에 있는 문서 비교. 
            int nowdoc = q.front().first;
            int nowprio = q.front().second;
            q.pop();
            // 남은 문서 중 중요도 제일 큰것과 비교.
            // 중요도 제일 큰 문서가 현재 큐의 맨 앞에 있었다면 
            if( pq.top()==nowprio){
                printnum++;        // 프린트 
                pq.pop();        // pq에서 제거 
                if( nowdoc == m ){
                    // 현재 프린트 한 문서가 인덱스 m이라면
                    // 몇번째로 인쇄되는지 출력 
                    cout<<printnum<<'\n';
                    break;
                }
            }
            // 중요도 제일 큰 문서가 아니라면 다시 큐의 맨 뒤로 넣어준다. 
            else{
                q.push(make_pair(nowdoc, nowprio));
            }
        }
    }
    return 0;
}
 cs

##

우선순위 큐를 사용하지 않고, 벡터나 배열에 중요도만 내림차순으로 정렬해서 사용해도 똑같겠군!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10830번 :: 행렬 제곱  (0) 2019.12.27
BOJ 10816번 :: 숫자 카드 2  (0) 2019.12.27
BOJ 11866번 :: 조세퍼스 문제 0  (0) 2019.12.26
BOJ 17298번 :: 오큰수  (0) 2019.12.26
BOJ 1874번 :: 스택 수열  (0) 2019.12.25

#문제

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

 

11866번: 조세퍼스 문제 0

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,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
#include <iostream>
#include <queue>
using namespace std;
 
int main(){
    int n, k;
    cin>>n>>k;
    queue<int> q;
    
    // 1~n까지의 수를 큐에 push 
    for(int i=1; i<=n; i++){
        q.push(i);
    }
    
    cout<<'<';
    while(true){
        for(int i=1; i<=k; i++){
            int tmp = q.front();
            q.pop();
            if(i!=k){
                q.push(tmp);
            }
            else{
                cout<<tmp;
                if( !q.empty())cout<<", ";
            }
        }
        if( q.empty()) break;
    }
    cout<<'>';
 
    return 0;
} 
cs

##

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10816번 :: 숫자 카드 2  (0) 2019.12.27
BOJ 1966번 :: 프린터 큐  (0) 2019.12.27
BOJ 17298번 :: 오큰수  (0) 2019.12.26
BOJ 1874번 :: 스택 수열  (0) 2019.12.25
BOJ 2740번 :: 행렬 곱셈  (0) 2019.12.25

#문제

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

 

17298번: 오큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,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
#include <iostream>
#include <stack>
using namespace std;
 
int n;
int a[1000001];            // 인덱스 1~1,000,000을 사용한다 
int answer[1000001];
 
int main(){
    cin>>n;
    stack<int> st;
    // 오큰수를 판별할 수들을 a[i]에 저장한다. 
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    
    // 수열에 들어갈 수 있는 어느 원소보다 큰 값을 스택에 push 
    st.push(1000002);
    // 수열을 뒤에서부터 앞으로 탐색한다. 
    for(int i=n; i>0; i--){
        // 스택의 top에 현재 수열값보다 작은 값이 있다면
        // 더 큰 수가 나올때까지 pop한다.
        // -> 현재 수열값 뒤쪽에 존재하는 가장 최근의 더 큰 값이 나온다. 
        if( st.top()<=a[i] ){
            while(true){
                st.pop();
                if( st.top()>a[i] ) break;
            }
        }
        // 앞에서 더 작은값이 존재해서 pop연산 진행 후에
        // 바로 a[i]의 오큰수 판단을 위해서 else대신 if문을 사용.
        // 스택 top값 > 수열값이면
        // answer[i]에 a[i]의 오큰수를 저장하고
        // a[i]를 스택에 push한다. 
        if( st.top()>a[i]){
            if( st.top()==1000002 ){
                answer[i] = -1;
            }
            else{
                answer[i] = st.top();
            }
            st.push(a[i]);
        }
    }
    
    // 수열의 오큰수를 출력한다. 
    for(int i=1; i<=n; i++){
        cout<<answer[i]<<' ';
    }
    
    return 0;
}
 cs
더보기
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
#include <iostream>
#include <stack>
using namespace std;
 
int n;
int a[1000001];            // 인덱스 1~1,000,000을 사용한다 
 
int main(){
    cin>>n;
    stack<int> st;
    // 오큰수를 판별할 수들을 a[i]에 저장한다. 
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    
    // 수열에 들어갈 수 있는 어느 원소보다 큰 값을 스택에 push 
    st.push(1000002);
    // 수열을 뒤에서부터 앞으로 탐색한다. 
    for(int i=n; i>0; i--){
        // 스택의 top에 현재 수열값보다 작은 값이 있다면
        // 더 큰 수가 나올때까지 pop한다.
        // -> 현재 수열값 뒤쪽에 존재하는 가장 최근의 더 큰 값이 나온다. 
        if( st.top()<=a[i] ){
            while(true){
                st.pop();
                if( st.top()>a[i] ) break;
            }
        }
        // 앞에서 더 작은값이 존재해서 pop연산 진행 후에
        // 바로 a[i]의 오큰수 판단을 위해서 else대신 if문을 사용.
        // 스택 top값 > 수열값이면
        // tmp에 a[i]값을 보관. 
        // a[i]에 a[i]의 오큰수(스택의 top값)를 저장하고
        // tmp에 보관해둔 a[i]를 스택에 push한다. 
        if( st.top()>a[i]){
            int tmp=a[i]; 
            if( st.top()==1000002 ){
                a[i] = -1;
            }
            else{
                a[i] = st.top();
            }
            st.push(tmp);
        }
    }
    
    // 수열의 오큰수를 출력한다. 
    for(int i=1; i<=n; i++){
        cout<<a[i]<<' ';
    }
    
    return 0;
}
 csd

a[i]값을 tmp에 저장해두고, a[i]에 스택의 top값을 저장,

스택에 tmp값을 push하면 answer[1000001]사이즈 배열을 추가로 사용하지 않아도 되므로 메모리 사용을 줄일 수 있다.

( 약 12000kb -> 약 8000kb 로 메모리 사용이 줄어들었음. )

##

수열의 뒤에서부터 앞으로 스택에 push하며 판단하는 것이 포인트!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1966번 :: 프린터 큐  (0) 2019.12.27
BOJ 11866번 :: 조세퍼스 문제 0  (0) 2019.12.26
BOJ 1874번 :: 스택 수열  (0) 2019.12.25
BOJ 2740번 :: 행렬 곱셈  (0) 2019.12.25
BOJ 11401번 :: 이항 계수 3  (0) 2019.12.25

#문제

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

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
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int nums[100000];
// c/c++에서는 a[100000] 크기의 배열을 지역변수로 선언할 수 없다고해서 전역변수로 선언 
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>nums[i];        // 인덱스 1~n 사용 
    }
    
    // 1~n의 수열을 만들어보자
    // 스택에 push 하는 순서는 반드시 오름차순을 지킨다
    // 임의의 수열을 스택을 이용해 그 수열을 만들 수 있으면push/pop연산 출력해서 표현하고
    // 만들수없으면 NO를 출력한다.
    stack<int> st;
    queue<char> q;
    int i=1, j=0;
    
    while( j<n ){
        // 스택이 비어있지않고 top==nums[j]일때 
        while( !st.empty() && st.top() == nums[j] ){
            st.pop();
            q.push('-');
            j++;
        }
        // nums[j]까지의 수(i)를 스택에 push한다.
        if( nums[j]>=i ){
            while(true){
                if( nums[j]<i ) break;
                st.push(i);
                q.push('+');
                i++;    
            }
        }
        // nums[j]까지의 수가 이미 스택에 들어갔는데
        // 스택이 비어있지않고, top에 존재하는 수가 nums[j]보다 크다면
        // 이 수열은 스택을 이용해서 만들 수 없으므로 NO를 출력 
        else if( !st.empty() && st.top()>nums[j] ){
            cout<<"NO\n";
            return 0;
        }
    }
    while(!q.empty()){
        cout<<q.front()<<'\n';
        q.pop();
    }
    return 0;
}
 cs

아래 코드처럼 수정하니 조금 더 깔끔한것같다.

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
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int nums[100000];
// c/c++에서는 a[100000] 크기의 배열을 지역변수로 선언할 수 없다고해서 전역변수로 선언 
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>nums[i];        // 인덱스 1~n 사용 
    }
    
    // 1~n의 수열을 만들어보자
    // 스택에 push 하는 순서는 반드시 오름차순을 지킨다
    // 임의의 수열을 스택을 이용해 그 수열을 만들 수 있으면push/pop연산 출력해서 표현하고
    // 만들수없으면 NO를 출력한다.
    stack<int> st;
    queue<char> q;    // '+'와 '-'를 저장한다. 
    int i=1, j=0;
    
    // 1부터 n까지의 수를 차례로 스택에 push하면서
    // 수열 현재값과 같으면 스택에서 pop하는 방식으로 비교해나간다. 
    for(int i=1; i<=n; i++){
        st.push(i);
        q.push('+');
        // 스택의 최상단과 수열 현재값 같으면
        // 비교하고, 스택에서 pop할 수 있는만큼 pop한다 
        while( !st.empty()&&st.top()==nums[j] ){
            st.pop();
            q.push('-');
            j++;
        }
    }
    
    // n까지 스택에 push 후에 수열과 같다면 pop하는 방식에서
    // 스택에 값이 남아있다면 해당 수열을 스택을 이용해서 만들수없다는 뜻 
    if( !st.empty() ){
        cout<<"NO\n";
        return 0;
    }
    // 스택이 비어있다면 해당 수열을 만들수 있다는 뜻
    // 큐에 저장된 것을 출력한다. 
    else{
        while(!q.empty()){
            cout<<q.front()<<'\n';
            q.pop();
        }
    }
    return 0;
}
cs

##

int a[100,000] 정도 크기의 배열은 main 함수 내에서 지역 변수로 선언하면 런타임 에러/ 메모리 초과 오류가 발생할 수 있다는 글을 읽고(https://www.acmicpc.net/board/view/32251) 전역 변수로 선언했더니 에러를 해결하고 AC 판정을 받을 수 있었다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11866번 :: 조세퍼스 문제 0  (0) 2019.12.26
BOJ 17298번 :: 오큰수  (0) 2019.12.26
BOJ 2740번 :: 행렬 곱셈  (0) 2019.12.25
BOJ 11401번 :: 이항 계수 3  (0) 2019.12.25
BOJ 1920번 :: 수 찾기  (0) 2019.12.25

+ Recent posts

티스토리툴바