반응형

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

 

2749번: 피보나치 수 3

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 아래의 식을 바탕으로 $F_{n}$의 값을 구할 수 있습니다.

 

$\begin{pmatrix}
1 &  1\\
1 &  0\\
\end{pmatrix}^{n} = \begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1} \\
\end{bmatrix}$

 

2. 분할 정복을 활용하여 n이 2의 배수라면 $F_{n} = F_{\frac{n}{2}}\times F_{\frac{n}{2}}$ 아니라면 $F_{n-1}\times F_{1}$을 통해 구해줍니다.

 

3. 메모이제이션을 활용하여 각각의 $F_{i}$을 1,000,000으로 나눈 나머지 값을 저장합니다.

 

4. $F_{n}$의 [0, 1] 항을 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<map>
#define M 1000000
#define ll long long
 
using namespace std;
 
ll n;
vector<vector<ll>> mat = { {1,1},{1,0} };
map<ll, vector<vector<ll>>> m;
 
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b)
{
    vector<vector<ll>> ret = { {0,0},{0,0} };
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ret[i][j] = (((a[i][0] % M) * (b[0][j] % M)) % M + ((a[i][1] % M) * (b[1][j] % M)) % M) % M;
        }
    }
 
    return ret;
}
 
vector<vector<ll>> conquer(ll n)
{
    if (m[n].size() != 0) return m[n];
    if (n == 1) return mat;
    if (n == 0) return { {1,0},{0,1} };
    if (n % 2 == 0) {
        return m[n] = mul(conquer(n / 2), conquer(n / 2));
    }
    else {
        return m[n] = mul(conquer(n - 1), conquer(1));
    }
}
 
int main()
{
    scanf("%lld", &n);
 
    vector<vector<ll>> ans = conquer(n);
    
    printf("%d", ans[0][1]);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2668번 - 숫자고르기 (C++)  (0) 2023.04.16
[ 백준 ] 1253번 - 좋다 (C++)  (0) 2023.04.15
[ 백준 ] 2436번 - 공약수 (C++)  (0) 2023.04.13
[ 백준 ] 1484번 - 다이어트 (C++)  (0) 2023.04.12
[ 백준 ] 20366번 - 같이 눈사람 만들래? (C++)  (0) 2023.04.11
반응형

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

 

10090번: Counting Inversions

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 입력받은 수를 인덱스로 segment tree를 업데이트합니다.

 

2. 입력받은 수 + 1부터 N까지 구간 합을 ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll segTree[2100000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (s > idx || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx)
{
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    ll ans = 0;
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
 
        updateTree(1, 1, N, n);
        ans += sumTree(1, 1, N, n + 1, N);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
반응형

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

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

분할 정복을 통해서 문제를 풀었습니다.

 

1. 원하는 부분의 숫자가 모두 같은 지 판단합니다.

 

2. 숫자가 다르다면 다시 9구역으로 나누어 1번을 반복합니다.

 

3. 숫자가 같다면 ans 배열에 1을 더해줍니다.

 

[ 소스 코드 ]

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>
 
using namespace std;
 
int N;
int arr[2200][2200];
int ans[3];
 
void conquer(int y1, int y2, int x1, int x2)
{
    int flag = 0;
    int cur = arr[y1][x1];
    for (int i = y1; i < y2; i++) {        //모두 같은 수인지
        for (int j = x1; j < x2; j++) {
            if (cur != arr[i][j]) {
                flag = 1;
                break;
            }
 
        }
    }
 
    int y = (y2 - y1) / 3;
    int x = (x2 - x1) / 3;
 
    if (flag == 0) {        //같은 수라면
        ans[cur + 1]++;
    }
    else {        //다른 수가 있다면
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                conquer(y1 + y * i, y1 + y * (i + 1), x1 + x * j, x1 + x * (j + 1));
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    conquer(0, N, 0, N);
 
    for (int i = 0; i < 3; i++) {
        printf("%d\n", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
반응형

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

 

1725번: 히스토그램

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은

www.acmicpc.net

 

 

[ 문제풀이 ]

 

다음과 같은 순서대로 문제를 풀어주시면 쉽게 답을 구할 수 있습니다.

 

1. push 하려는 막대의 높이가 s.top() 인덱스의 막대 높이보다 크거나 같다면 계속해서 스택을 쌓습니다. 

 

2. 만약 push 하려는 막대의 높이가 s.top() 인덱스의 막대 높이보다 작다면 s.top()이 push 하려는 막대 높이보다 커질 때까지 s.pop()을 해줍니다.

 

3. s.pop()을 할 때마다 직사각형의 넓이를 구하고 최댓값을 저장합니다.

 

다음 글은 세그먼트 트리와 분할 정복을 통해 문제를 푸는 방법입니다.

https://rudalsd.tistory.com/88?category=1064612 

 

[ 소스 코드 ]

 

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>
#include<stack>
 
using namespace std;
 
int N;
int arr[100005];
int ans;
 
int main()
{
    stack<int> s;
    s.push(0);
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= N + 1; i++) {
        while (!s.empty() && arr[i] < arr[s.top()]) {
            int cur = s.top();
            s.pop();
            int W = arr[cur] * (i - s.top() - 1);
            ans = max(ans, W);
        }
        s.push(i);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11725번 - 트리의 부모 찾기 (C++)  (0) 2022.07.31
반응형

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

 

6549번: 히스토그램에서 가장 큰 직사각형

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!!

https://rudalsd.tistory.com/51?category=1073064 

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

먼저 높이 값이 가장 작은 idx를 각각의 노드에 저장하는 세그먼트 트리를 만듭니다. 그 후 일정 구간에서 가장 작은 높이를 가지는 idx를 구하는 함수를 만든 후 그 idx를 기준으로 왼쪽 오른쪽으로 나누어 분할 정복을 해주시면 됩니다.

 

다음 글은 스택을 활용하여 문제를 푸는 방법입니다.

https://rudalsd.tistory.com/89?category=1064612 

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<cmath>
 
#define ll long long
 
using namespace std;
 
int n;
int segTree[300000];
ll arr[100001];
ll ans;
 
int makeTree(int node, int start, int end)        //세그먼트 트리 만들기
{
    if (start == end) {        //리프노드
        return segTree[node] = start;
    }
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);        //왼쪽 자식 노드
    int right = makeTree(node * 2 + 1, mid + 1, end);    //오른쪽 자식 노드
 
    return segTree[node] = arr[left] > arr[right] ? right : left;
}
 
int find(int node, int start, int end, int sidx, int eidx)    //최소 높이의 idx return
{
    if (eidx < start || sidx > end) return 0;    //범위에 완전히 포함되지 않을 때
    if (start >= sidx && end <= eidx) return segTree[node];    //범위에 완전히 포함될 때
    //범위에 일부 포함될 때
    int mid = (start + end) / 2;
    int left = find(node * 2, start, mid, sidx, eidx);
    int right = find(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left == 0) return right;
    if (right == 0) return left;
    return arr[left] > arr[right] ? right : left;
}
 
void getMax(int start, int end)
{
    if (start > end) return;
    int min = find(1, 1, n, start, end);
 
    ll W = arr[min] * (end - start + 1);
    ans = max(ans, W);
 
    getMax(start, min - 1);
    getMax(min + 1, end);
}
 
int main()
{
    while (1)
    {
        ans = 0;
        scanf("%d", &n);
        if (n == 0)break;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &arr[i]);
        }
 
        makeTree(1, 1, n);
 
        getMax(1, n);
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11725번 - 트리의 부모 찾기 (C++)  (0) 2022.07.31
[ 백준 ] 11444번 - 피보나치 수 6 (C++)  (0) 2022.07.30
반응형

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

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

일반적인 분할 정복 문제와 똑같이 풀면 됩니다!

 

제곱수 n이 짝수일 때 $A^{\frac{n}{2}}\times A^{\frac{n}{2}}$ 홀수일 때 $A^{n-1}\times A$의 방식으로 계산해나가면 O(logn)의 시간 복잡도로 풀 수 있습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
 
#define ll long long
 
using namespace std;
 
int N;
ll B;
 
vector<vector<int>> A;        //행렬 A
vector<vector<int>> ans;    //정답 행렬
 
vector<vector<int>> gop(vector<vector<int>> a, vector<vector<int>> b)        //행렬 곱
{
    vector<vector<int>> ret;
    ret.resize(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int sum = 0;
            for (int k = 0; k < N; k++) {
                sum += (a[i][k] * b[k][j]) % 1000;
                sum %= 1000;
            }
            ret[i].push_back(sum);
        }
    }
 
    return ret;
}
 
vector<vector<int>> conquer(ll num)        //분할 정복
{
    if (num == 1) {
        return A;
    }
 
    if (num % 2 == 0) {
        vector<vector<int>> temp = conquer(num / 2);
        return gop(temp, temp);
    }
    else {
        return gop(conquer(num - 1), conquer(1));
    }
}
 
int main()
{
    cin >> N >> B;
 
    A.resize(N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            cin >> num;
            A[i].push_back(num);
        }
    }
 
    ans = conquer(B);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << ans[i][j] % 1000 << " ";
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2150번 - Strongly Connected Component (C++)  (0) 2022.07.24
[ 백준 ] 1948번 - 임계경로 (C++)  (0) 2022.07.22
[ 백준 ] 1786번 - 찾기 (C++)  (0) 2022.07.20
[ 백준 ] 1761번 - 정점들의 거리 (C++)  (0) 2022.07.18
[ 백준 ] 1708번 - 볼록 껍질 (C++)  (0) 2022.07.17

+ Recent posts

티스토리툴바