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

 

10826번: 피보나치 수 4

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 ��

www.acmicpc.net

 

이 문제는 BOJ2407 조합 문제와 같이 피보나치 10000 의 자릿수가 2000 이 넘어가기 때문에 c++ 표준 자료형의 범위로는 표현할 수 없다. 마찬가지로 string 덧셈으로 풀 수 있는데, 이전 BOJ2407 번에서 구현한 string 덧셈이 비효율적이라 시간초과가 난다. 따라서 string 덧셈과정에서 역순으로 += 연산을 최대한 이용할 수 있도록 구현하여 시간제한 안에 풀 수 있도록 구현하였다.

 

새롭게 안 사실인데, 피보나치 4 문제의 질문 게시글 에서 문자열의 덧셈 방법 s = s + "string" 과 s += "string" 이 다르다는 것을 설명한다. 첫 번째 방법(s = s + "string") 은 string 을 새롭게 복사하기 때문에 O(s.size()^2) 의 시간이 걸린다고 한다. 두 번째 방법은 단순히 이어 붙이기 때문에, 시간적으로 매우 차이가 날 수 있다.

 

 

 

소스코드

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
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
string s_add(string s1, string s2){
    string ret = "";
 
    int s1len = s1.length(), s2len = s2.length();
    int is_carry = 0;
    int i;
    for(i = 0; i<s2len; i++){
        char s = s1[i]-'0' + s2[i] + is_carry;
        if(s > '9'){
            is_carry = 1;
            s -= 10;
        } else {
            is_carry = 0;
        }
        ret += s;
    }
 
    for(int j=i; j<s1len; j++){
        char s = s1[j] + is_carry;
        if(s > '9'){
            is_carry = 1;
            s -= 10;
        } else {
            is_carry = 0;
        }
        ret += s;
    }
 
    if(is_carry){
        ret += "1";
    }
    return ret;
}
vector< string >v(10001);
int main(){
    int n;
    cin>>n;
    for(int i=0; i<=10000; i++){
        v[i] = "0";
    }
    v[2= v[1= "1";
    for(int i=3; i<=10000;i++){
        v[i] = s_add(v[i-1], v[i-2]);
    }
    reverse(v[n].begin(), v[n].end());
    cout<< v[n] <<endl;
    return 0;
}
cs

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03

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

 

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부

www.acmicpc.net

 

이 문제는 위상정렬로 풀 수 있는 문제이다. 위상 정렬은 주로 게임에서 스킬트리와 같은 즉, 선행되어야 하는 작업이 있을 때의 순서를 어떻게 처리해야 빠른지를 풀 때 사용하는 알고리즘이다. 위상정렬의 구현은 그래프 구조에서 in-direction 의 갯수를 저장하는 배열이 가장 핵심이다. 즉 어떤 노드 K 번에 들어오는 간선의 수가 3개가 있을 때, ind[K] = 3 처럼 저장한 뒤, ind[i] 값이 0인 정점부터 큐(queue)에 넣고 순차적으로 탐색해가면 된다.

 

 

위 그림으로 설명하면

 1. ind 값이 0 인 1번 3번 노드가 queue에 넣는다.
 2. 큐에 가장 앞에 있는 노드를 방문(1 번) 한 후, 이 노드에 연결된 (2 번으로의)간선을 돌면서 ind[ graph[cur][next] ] 의 값을 -1 해준다.
     ( 그림에선 2번으로의 간선이므로, ind[2]--; )
 3. 만약 2번의 과정을 통해서 ind 값이 0 이 되면(ind[ graph[cur][next] ] == 0) 해당 노드를 queue에 push 한다.
 4. 2~3번을 반복

 

 

 

소스코드

 

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<stdio.h>
#include<queue>
#include<vector>
 
using namespace std;
int inline max(int a, int b){return a>b?a:b;}
int n, t[501], ind[501], ans[501];
vector<int> v[501];
 
int main(){
    scanf("%d"&n);
    int p;
    for(int i=1;i<=n;i++){
        scanf("%d"&t[i]);
        while(scanf("%d"&p) == 1){
            if(p == -1break;
            v[p].push_back(i);
            ind[i]++;
        }
    }
 
    queue< pair<intint> > q;
    for(int i=1;i<=n;i++){
        if(ind[i] == 0){
            q.push(make_pair(i, t[i]));
            ans[i] = t[i];
        }
    }
 
    while(!q.empty()){
        int cur = q.front().first; 
        int curt = q.front().second;
        q.pop();
        for(int i=0; i<v[cur].size(); i++){
            ind[ v[cur][i] ]--;
            ans[ v[cur][i] ] = max(ans[v[cur][i]], curt + t[ v[cur][i] ]);
            if(ind[ v[cur][i] ] == 0){
                q.push(make_pair(v[cur][i], ans[ v[cur][i] ] ));
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}
 
 
cs

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02

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

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

이 문제는 100 C 50 조합 값이 long long int 를 벗어나는 약 30자리 수 정도이기 때문에, 다른 방법으로 덧셈을 계산해야 한다. 따라서 덧셈을 위해 string 클래스를 이용해 문자열끼리의 더하기를 구현하였다.

 

다음은 100_C_n 의 조합의 결과 : 

(100C1) : 1 + 99 = 100
(100C2) : 99 + 4851 = 4950
(100C3) : 4851 + 156849 = 161700
(100C4) : 156849 + 3764376 = 3921225
(100C5) : 3764376 + 71523144 = 75287520
(100C6) : 71523144 + 1120529256 = 1192052400
(100C7) : 1120529256 + 14887031544 = 16007560800
(100C8) : 14887031544 + 171200862756 = 186087894300
(100C9) : 171200862756 + 1731030945644 = 1902231808400
(100C10) : 1731030945644 + 15579278510796 = 17310309456440
(100C11) : 15579278510796 + 126050526132804 = 141629804643600
(100C12) : 126050526132804 + 924370524973896 = 1050421051106700
(100C13) : 924370524973896 + 6186171974825304 = 7110542499799200
(100C14) : 6186171974825304 + 38000770702498296 = 44186942677323600
(100C15) : 38000770702498296 + 215337700647490344 = 253338471349988640
(100C16) : 215337700647490344 + 1130522928399324306 = 1345860629046814650
(100C17) : 1130522928399324306 + 5519611944537877494 = 6650134872937201800
(100C18) : 5519611944537877494 + 25144898858450330806 = 30664510802988208300
(100C19) : 25144898858450330806 + 107196674080761936594 = 132341572939212267400
(100C20) : 107196674080761936594 + 428786696323047746376 = 535983370403809682970
(100C21) : 428786696323047746376 + 1613054714739084379224 = 2041841411062132125600
(100C22) : 1613054714739084379224 + 5719012170438571889976 = 7332066885177656269200
(100C23) : 5719012170438571889976 + 19146258135816088501224 = 24865270306254660391200
(100C24) : 19146258135816088501224 + 60629817430084280253876 = 79776075565900368755100
(100C25) : 60629817430084280253876 + 181889452290252840761628 = 242519269720337121015504
(100C26) : 181889452290252840761628 + 517685364210719623706172 = 699574816500972464467800
(100C27) : 517685364210719623706172 + 1399667836569723427057428 = 1917353200780443050763600
(100C28) : 1399667836569723427057428 + 3599145865465003098147672 = 4998813702034726525205100
(100C29) : 3599145865465003098147672 + 8811701946483283447189128 = 12410847811948286545336800
(100C30) : 8811701946483283447189128 + 20560637875127661376774632 = 29372339821610944823963760
(100C31) : 20560637875127661376774632 + 45764000431735762419272568 = 66324638306863423796047200
(100C32) : 45764000431735762419272568 + 97248500917438495140954207 = 143012501349174257560226775
(100C33) : 97248500917438495140954207 + 197443926105102399225573693 = 294692427022540894366527900
(100C34) : 197443926105102399225573693 + 383273503615787010261407757 = 580717429720889409486981450
(100C35) : 383273503615787010261407757 + 711793649572175876199757263 = 1095067153187962886461165020
(100C36) : 711793649572175876199757263 + 1265410932572757113244012912 = 1977204582144932989443770175
(100C37) : 1265410932572757113244012912 + 2154618614921181030658724688 = 3420029547493938143902737600
(100C38) : 2154618614921181030658724688 + 3515430371713505892127392912 = 5670048986634686922786117600
(100C39) : 3515430371713505892127392912 + 5498493658321124600506947888 = 9013924030034630492634340800
(100C40) : 5498493658321124600506947888 + 8247740487481686900760421832 = 13746234145802811501267369720
(100C41) : 8247740487481686900760421832 + 11868699725888281149874753368 = 20116440213369968050635175200
(100C42) : 11868699725888281149874753368 + 16390109145274293016493707032 = 28258808871162574166368460400
(100C43) : 16390109145274293016493707032 + 21726423750712434928840495368 = 38116532895986727945334202400
(100C44) : 21726423750712434928840495368 + 27651812046361280818524266832 = 49378235797073715747364762200
(100C45) : 27651812046361280818524266832 + 33796659167774898778196326128 = 61448471214136179596720592960
(100C46) : 33796659167774898778196326128 + 39674339023040098565708730672 = 73470998190814997343905056800
(100C47) : 39674339023040098565708730672 + 44739148260023940935799206928 = 84413487283064039501507937600
(100C48) : 44739148260023940935799206928 + 48467410615025936013782474172 = 93206558875049876949581681100
(100C49) : 48467410615025936013782474172 + 50445672272782096667406248628 = 98913082887808032681188722800
(100C50) : 50445672272782096667406248628 + 50445672272782096667406248628 = 100891344545564193334812497256
(100C51) : 50445672272782096667406248628 + 48467410615025936013782474172 = 98913082887808032681188722800
(100C52) : 48467410615025936013782474172 + 44739148260023940935799206928 = 93206558875049876949581681100
(100C53) : 44739148260023940935799206928 + 39674339023040098565708730672 = 84413487283064039501507937600
(100C54) : 39674339023040098565708730672 + 33796659167774898778196326128 = 73470998190814997343905056800
(100C55) : 33796659167774898778196326128 + 27651812046361280818524266832 = 61448471214136179596720592960
(100C56) : 27651812046361280818524266832 + 21726423750712434928840495368 = 49378235797073715747364762200
(100C57) : 21726423750712434928840495368 + 16390109145274293016493707032 = 38116532895986727945334202400
(100C58) : 16390109145274293016493707032 + 11868699725888281149874753368 = 28258808871162574166368460400
(100C59) : 11868699725888281149874753368 + 8247740487481686900760421832 = 20116440213369968050635175200
(100C60) : 8247740487481686900760421832 + 5498493658321124600506947888 = 13746234145802811501267369720
(100C61) : 5498493658321124600506947888 + 3515430371713505892127392912 = 9013924030034630492634340800
(100C62) : 3515430371713505892127392912 + 2154618614921181030658724688 = 5670048986634686922786117600
(100C63) : 2154618614921181030658724688 + 1265410932572757113244012912 = 3420029547493938143902737600
(100C64) : 1265410932572757113244012912 + 711793649572175876199757263 = 1977204582144932989443770175
(100C65) : 711793649572175876199757263 + 383273503615787010261407757 = 1095067153187962886461165020
(100C66) : 383273503615787010261407757 + 197443926105102399225573693 = 580717429720889409486981450
(100C67) : 197443926105102399225573693 + 97248500917438495140954207 = 294692427022540894366527900
(100C68) : 97248500917438495140954207 + 45764000431735762419272568 = 143012501349174257560226775
(100C69) : 45764000431735762419272568 + 20560637875127661376774632 = 66324638306863423796047200
(100C70) : 20560637875127661376774632 + 8811701946483283447189128 = 29372339821610944823963760
(100C71) : 8811701946483283447189128 + 3599145865465003098147672 = 12410847811948286545336800
(100C72) : 3599145865465003098147672 + 1399667836569723427057428 = 4998813702034726525205100
(100C73) : 1399667836569723427057428 + 517685364210719623706172 = 1917353200780443050763600
(100C74) : 517685364210719623706172 + 181889452290252840761628 = 699574816500972464467800
(100C75) : 181889452290252840761628 + 60629817430084280253876 = 242519269720337121015504
(100C76) : 60629817430084280253876 + 19146258135816088501224 = 79776075565900368755100
(100C77) : 19146258135816088501224 + 5719012170438571889976 = 24865270306254660391200
(100C78) : 5719012170438571889976 + 1613054714739084379224 = 7332066885177656269200
(100C79) : 1613054714739084379224 + 428786696323047746376 = 2041841411062132125600
(100C80) : 428786696323047746376 + 107196674080761936594 = 535983370403809682970
(100C81) : 107196674080761936594 + 25144898858450330806 = 132341572939212267400
(100C82) : 25144898858450330806 + 5519611944537877494 = 30664510802988208300
(100C83) : 5519611944537877494 + 1130522928399324306 = 6650134872937201800
(100C84) : 1130522928399324306 + 215337700647490344 = 1345860629046814650
(100C85) : 215337700647490344 + 38000770702498296 = 253338471349988640
(100C86) : 38000770702498296 + 6186171974825304 = 44186942677323600
(100C87) : 6186171974825304 + 924370524973896 = 7110542499799200
(100C88) : 924370524973896 + 126050526132804 = 1050421051106700
(100C89) : 126050526132804 + 15579278510796 = 141629804643600
(100C90) : 15579278510796 + 1731030945644 = 17310309456440
(100C91) : 1731030945644 + 171200862756 = 1902231808400
(100C92) : 171200862756 + 14887031544 = 186087894300
(100C93) : 14887031544 + 1120529256 = 16007560800
(100C94) : 1120529256 + 71523144 = 1192052400
(100C95) : 71523144 + 3764376 = 75287520
(100C96) : 3764376 + 156849 = 3921225
(100C97) : 156849 + 4851 = 161700
(100C98) : 4851 + 99 = 4950
(100C99) : 99 + 1 = 100

 

 

소스코드

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
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;
int n,m;
vector< string > dp[101];
 
string s_add(string s1, string s2){
    string ret = "";
 
    int s1len = s1.length()-1, s2len = s2.length()-1;
    int is_carry = 0;
    while( s1len >= 0 || s2len >= 0){
        int s = ( s1len >= 0 ? s1[s1len]-'0' : 0 ) + ( s2len >= 0 ? s2[s2len]-'0' : 0+ is_carry;
        is_carry = s / 10;
        s %= 10;
 
        ret = (char)(s+'0'+ ret;
        s1len--, s2len--;
    }
    if(is_carry){
        ret = (char)('0'+is_carry) + ret;
    }
    return ret;
}
 
int main(){
    scanf("%d %d",&n,&m);
    
    for(int i=1; i<=n; i++){
        dp[i].resize(n+1);
        for(int j=1;j<n;j++){
            dp[i][j] = "0";
        }
        dp[i][0= dp[i][i] = "1";
    }
    for(int i=2; i<= n; i++){
        for(int j=1; j < i; j++){
            dp[i][j] = s_add(dp[i-1][j-1], dp[i-1][j]);
            // printf("(%dC%d) : %s + %s = %s\n", i,j, dp[i-1][j-1].c_str(), dp[i-1][j].c_str(), dp[i][j].c_str());
        }
    }
    printf("%s\n", dp[n][m].c_str());
    return 0;
}
cs

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02
BOJ 4811 알약  (0) 2020.08.28

+ Recent posts