"2747번 : 피보나치 수" 를 해결했을때와 원리와 소스코드 모두 같으므로 다음 링크로 대체합니다.


http://rehu.tistory.com/8


(2748번이 n의 범위가 더 큰 것 제외 2747번과 차이 없음)


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

1003번 : 피보나치 함수  (0) 2018.04.01
2749번 : 피보나치 수 3  (0) 2018.04.01
2747번 : 피보나치 수  (0) 2018.04.01
5430번 : AC  (0) 2018.03.28
1021번 : 회전하는 큐  (0) 2018.03.27

Backjoon Online Judge 

"2747번 : 피보나치 수" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2747


피보나치수는 재귀를 이용해도 구할 수 있지만 연산을 빠르게 하기 위해 배열과 반복문을 이용하였습니다.

(피보나치 수를 구하는 여러가지 방법은 https://www.acmicpc.net/blog/view/28 에 자세히 설명 되어 있습니다.)


 - n <= 45 이므로 int 범위에 속하지만 편의상 long long int로 지정하였습니다. 


코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
 
using namespace std;
 
int main() {
    long long int fibo[100] = { 0, 1 };
    int n;
    
    cin >> n;
    for (int i = 2; i <= n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    cout << fibo[n] << "\n";
    return 0;
}

cs



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2749번 : 피보나치 수 3  (0) 2018.04.01
2748번 : 피보나치 수 2  (0) 2018.04.01
5430번 : AC  (0) 2018.03.28
1021번 : 회전하는 큐  (0) 2018.03.27
10866번 : 덱  (0) 2018.03.24

Backjoon Online Judge 

"5430번 : AC" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/5430


문제에서 뒤집기 연산을 빠르고 쉽게 수행하기 위해 Deque를 이용하였습니다.


 - 일단 최대 100,000개의 p를 한번에 입력받기 위해 100,002 짜리 char형 배열을 선언하였습니다.

(널문자를 고려하여 100,002개 선언)


 - 이후 주어지는 배열을 저장하기 위해 400,002 크기의 char형 배열을 선언하였습니다.

((x의 최댓값이 100이므로 구분자(,) 포함)4바이트 * 100,000 + 2 (널문자 & 마지막 구분자))


 - 저장 된 배열은 strtok를 이용하여 구분하였고, 구분 된 배열은 atoi함수로 변환하여 저장하였습니다.

(strtok -> cstring, atoi -> cstdlib 라이브러리 이용)


 - 계산부분은 뒤집기의 경우 (앞에서 부터 읽도록 / 뒤에서 부터 읽도록) 상호 변환하도록 하였고

   버리기의 경우 큐의 맨 앞부분을 POP 하는 방식으로 구현하였습니다.


많은 예외처리로 코드가 다소 복잡합니다.

코드는 C++로 작성하였습니다.

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
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <cstdlib>
 
using namespace std;
 
int main() {
    int T, n; 
    char func[100002];
    char numTmp[400002];
    int lr;    //1이면 왼쪽부터, 0이면 에러, -1이면 오른쪽부터
 
    cin >> T;
    while (T--) {
        deque<int> dq;
        lr = 1;
        cin >> func >> n >> numTmp;
 
        //char* context = NULL;
        //char* num = strtok_s(numTmp, "[],", &context);
        char *num = strtok(numTmp, "[],");
        while(num != NULL) {
            dq.push_back(atoi(num));
            //num = strtok_s(NULL, "[],", &context);
            num = strtok(NULL, "[],");
        }
 
        //계산부분
        int len = strlen(func);
        for (int i = 0; i < len; i++) {
            if (func[i] == 'R') {
                lr *= -1;
            }
            else if (func[i] == 'D') {
                if (!dq.size()) {
                    lr = 0;
                    break;
                }
                if (lr == 1)
                    dq.pop_front();
                else
                    dq.pop_back();
            }
            else {
                cout << "impossible error\n";
                return -1;
            }
        }
 
        //출력부분
        if (lr == 0) {
            cout << "error\n";
        }
        else if (dq.size() == 0) {
            cout << "[]\n";
        }
        else if (lr == 1) {
            cout << "[";
            while (dq.size()-1) {
                cout << dq.front();
                cout << ",";
                dq.pop_front();
            }
            cout << dq.front() << "]\n";
        }
        else {
            cout << "[";
            while (dq.size() - 1) {
                cout << dq.back();
                cout << ",";
                dq.pop_back();
            }
            cout << dq.back() << "]\n";
        }
    }
    return 0;
}



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2748번 : 피보나치 수 2  (0) 2018.04.01
2747번 : 피보나치 수  (0) 2018.04.01
1021번 : 회전하는 큐  (0) 2018.03.27
10866번 : 덱  (0) 2018.03.24
1158번 : 조세퍼스 문제  (0) 2018.03.23

Backjoon Online Judge 

"1021번 : 회전하는 큐" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/1021


문제에서 3가지 연산을 쉽게 구현하기 위해 Queue 라이브러리를 사용하여 Deque를 만들었습니다.


 - 처음 위치는 위의 3가지 연산 과정에서 계속 바뀌므로 편의를 위해 처음 위치에 해당하는 '1'~'큐의 크기'까지를 각각 큐의 값으로 입력하였습니다.


 - 원소를 하나씩 뽑아낼 때 마다 다음번 뽑아내려는 위치를 얻고 이는 처음 큐에서의 위치이므로 현재 그 위치가 어디로 이동하였는지 확인하기 위해 큐의 처음 위치부터 접근하여 뽑아내야 할 위치를 찾았습니다. 


 - 뽑아내려는 할 위치를 찾은 경우 '뽑아낼 위치' 과 '큐의 크기 - 뽑아낼 위치' 를 비교하여 큐의 이동 방향을 정했습니다. (2, 3번 연산 횟수를 최소화 하기 위해)


- 위 문장을 보충설명 하자면 뽑아낼 위치로 접근하기 위한 방법은 큐를 왼쪽으로 계속 이동하여(2번 연산) 접근하거나, 큐를 오른쪽으로 계속 이동하여(3번 연산) 접근하는 방법이 있는데 뽑아낼 위치가 오른쪽이 있다면 (큐의 크기와 크게 차이나지 않는 곳) 3번 연산을 통해 해당 위치에 접근하는 것이 더 연산 횟수가 적어집니다.


- 위 과정을 M번 만큼 반복하여 2번, 3번 연산의 최솟값을 출력하게 됩니다.


코드는 C++로 작성하였습니다.

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 <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int main() {
    deque<int> dq;
    int N, M, tmp, i; 
    int answer = 0;
 
    cin >> N >> M;
 
    while (N--)
        dq.push_front(N+1);
 
    while (M--) {
        cin >> tmp;
        for (i = 0; i < dq.size(); i++) {
            if (dq[i] == tmp)
                break;
        }
 
        if (i < dq.size() - i) {
            while (i--) {
                dq.push_back(dq.front());
                dq.pop_front();
                answer++;
            }
        }
        else {
            i = dq.size() - i;
            while (i--) {
                dq.push_front(dq.back());
                dq.pop_back();
                answer++;
            }
        }
 
        dq.pop_front();
    }
 
    cout << answer << "\n";
    return 0;
}


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2747번 : 피보나치 수  (0) 2018.04.01
5430번 : AC  (0) 2018.03.28
10866번 : 덱  (0) 2018.03.24
1158번 : 조세퍼스 문제  (0) 2018.03.23
11866번 : 조세퍼스 문제 0  (0) 2018.03.23

Backjoon Online Judge 

"10866번 : 덱" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/10866


Deque의 각 명령을 구현하기 위해 Deque 라이브러리를 사용하였습니다.

 - string형 변수에 문자를 받아 일치 여부를 확인합니다.


코드는 C++로 작성하였습니다.

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
 
using namespace std;
 
int main() {
    deque<int> dq;
    int N, num;
    string str;
 
    scanf("%d",&N);
    while (N--) {
        cin >> str;
        if (str == "push_front") {
            scanf_s("%d", &num);
            dq.push_front(num);
        }
        else if (str == "push_back") {
            scanf_s("%d", &num);
            dq.push_back(num);
        }
        else if (str == "pop_front") {
            if (dq.empty()) {
                printf("-1\n");
                continue;
            }
            printf("%d\n", dq.front());
            dq.pop_front();
        }
        else if (str == "pop_back") {
            if (dq.empty()) {
                printf("-1\n");
                continue;
            }
            printf("%d\n", dq.back());
            dq.pop_back();
        }
        else if (str == "size") {
            printf("%d\n", dq.size());
        }
        else if (str == "empty") {
            printf("%d\n", dq.empty());
        }
        else if (str == "front") {
            if (dq.empty()) {
                printf("-1\n");
                continue;
            }
            printf("%d\n", dq.front());
        }
        else if (str == "back") {
            if (dq.empty()) {
                printf("-1\n");
                continue;
            }
            printf("%d\n", dq.back());
        }
    }
    return 0;
}



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

5430번 : AC  (0) 2018.03.28
1021번 : 회전하는 큐  (0) 2018.03.27
1158번 : 조세퍼스 문제  (0) 2018.03.23
11866번 : 조세퍼스 문제 0  (0) 2018.03.23
1966번 : 프린터 큐  (0) 2018.03.23

티스토리툴바