이 문제는 동적계획법으로 푸는 문제로

시간초과는  memoization으로 해결하면 되고

딱히 큰 어려움은 없는 문제이다.



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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[36];
 
unsigned long long t(int n) {
    if (n == 0)
        return result[n] = 1;
    if (result[n] > 0)
        return result[n];
    else {
        for (int i = 0; i < n + 1; i++)
            result[n] += t(i)*t(n - i - 1);
        return result[n];
    }
}
 
int main() {
    int input;
    cin >> input;
    cout << t(input);
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13

이 문제는 동적계획법으로

첫 번째 타일이 세로로 있을 때(n-1)랑 2개의 타일이 가로로 되어있을 때(n-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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[1001];
 
unsigned long long fibonacci(int n) {
    if (n == 1)
        return result[n] = 1;
    if (n == 2)
        return result[n] = 2;
    if (result[n] > 0)
        return result[n];
    else
        return result[n] = (fibonacci(n - 1) + fibonacci(n - 2))%10007;
}
 
int main() {
    int input;
    cin >> input;
    cout << fibonacci(input);
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17

이 문제는 간단한 동적 계획법을 이용하여 풀 수 있다.

어떤 동적계획법이든 마찬가지지만 시간초과가 제일 문제이다.

일단 이 문제는 확률과통계에서 나오는 조합을 이용하여 풀 수 있다.

eCr = e-1Cw-1 + e-1Cw (e = east, w = west) 공식을 이용하여 풀면 된다.

eC0 = 1일 때와 e==w일 때를 출구조건으로 하면 간단하게 풀 수 있다.

(memoization을 이용하지 않으면 시간초과가 뜨므로 주의한다.)



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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[30][30];
 
unsigned long long combination(int east, int west) {
    if (east == west || west == 0)
        return result[east][west] = 1;
    if (result[east][west] > 0)
        return result[east][west];
    else
        return result[east][west] = combination(east - 1, west - 1) + combination(east - 1, west);
}
 
int main() {
    int N;
    int west, east;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> west >> east;
        cout << combination(east, west) << endl;
    }
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03

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


비트마스크를 풀려고 이 문제를 건드렸으나

비트마스크를 이용해서 푸는 방법을 몰라서 배열로 케이스를 나눠서 풀었다.

예외케이스가 좀 있어서 해결하는데 시간이 좀 걸렸다.

 case문으로 하고 싶었으나 할줄모르겠다...ㅎㅎ



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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <cstdio>
#include <string>
#pragma warning(disable : 4996)
 
using namespace std;
int ary[101][101];
int main() {
    int N;
    scanf("%d", &N);
    string input;
    cin >> input;
    int a = 0, b = 0;                // a = row , b = column
                                    // 0 means ., 1 means |, 2 means -, 3 means +
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'D') {            // input = D
            if (a + 1 == N) continue;
            else {
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
 
                a += 1;
 
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
            }
        }
        else if (input[i] == 'U') {
            if (a - 1 < 0) continue;
            else {
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
 
                a -= 1;
 
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
            }
        }
        else if (input[i] == 'R') {
            if (b + 1 == N) continue;
            else {
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
 
                b += 1;
 
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
            }
        }
        else if (input[i] == 'L') {
            if (b - 1 < 0) continue;
            else {
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
 
                b -= 1;
                
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int output = ary[i][j];
            // 0 means ., 1 means |, 2 means -, 3 means +
            if (output == 0)
                printf("%c", 46);
            else if (output == 1)
                printf("%c", 124);
            else if (output == 2)
                printf("%c", 45);
            else if (output == 3)
                printf("%c", 43);
        }
        cout << endl;
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03

1. 


1
2
3
4
5
6
7
8
9
10
11
C:\Users\kei98\chromium\src>gn gen out/Default
ERROR at //build/toolchain/win/BUILD.gn:8:1: Can't load input file.
import("//build/config/win/visual_studio_version.gni")
^----------------------------------------------------
Unable to load:
  C:/Users/kei98/chromium/src/build/config/win/visual_studio_version.gni
I also checked in the secondary tree for:
  C:/Users/kei98/chromium/src/build/secondary/build/config/win/visual_studio_version.gni
See //BUILD.gn:71:1: which caused the file to be included.
group("gn_all") {
^----------------

dcs



이 현상은 BUILD.gn을 VS로 열면 import("//build/config/win/visual_studio_version.gni")라는 구문이 있는데
이 코드가 실행이 안된다는 코드로 //build/config/win/visual_studio_version.gni 파일을 만들어 줘야한다.

https://chromium.googlesource.com/chromium/src/+/lkgr/build/config/win에 들어가면

각종 코드를 볼 수 있는데 여기에 있는 코드를 그래도 복사해서 //build/config/win/visual_studio_version.gni 파일을 만들어주면된다.

(메모장으로 만든다음에 확장자명 바꾸면 됨.)



'Open Source > Chromium' 카테고리의 다른 글

[1] Fixed a Bug = 649938(tab to search hint still displayed when unfocused omnibox)  (0) 2017.09.21
Sites related to Chromium  (0) 2016.12.16
The Chromium Projects - Get the Code[start Chromium] & Error  (0) 2016.12.16

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


이 문제는 최단경로 문제이다. 보통은 다익스트라(Dijstra) 알고리즘을 쓰지만 이 문제의 경우에는 경로 가중치가 음수인 경우가 있으므로


벨만-포드(Bellman-Ford) 알고리즘 또는 플로이드-워셜(Floyd-Warshall) 알고리즘을 이용해야 한다.


두 개의 차이점은 구현 면에서 보면 플로이드-워셜은 이해하기는 힘드나 구현은 간단하다.


벨만-포드는 이해하기도 쉽고 구현도 그렇게 어렵지는 않지만 플로이드-워셜에 비하면 좀 더 복잡하다.


다음 시간 복잡도 면에서 보면, 벨만-포드는 O(E*V)이고 플로이드-워셜은 O(V^3)이다.


주어진 문제(E = 6000, V = 500)에 대입하면,


벨만-포드는 O(E*V) = 3000000정도이고 플로이드-워셜은 O(V^3) = 125000000정도로 시간 제한이 1초인것을 감안하면


플로이드-워셜은 시간 초과가 날 가능성이 높다.


그러므로 벨만-포드 알고리즘을 이용할 것이다.


https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

(위키피디아 Bellman-Ford Algorithm)

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

(위키백과 벨만-포드 알고리즘)


이 문제 난이도 면에서 보면 어렵지는 않으나


벨만-포드 알고리즘을 실제로 구현해보는 문제로 괜찮은 문제이다.


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 <cstdio>
#pragma warning (disable : 4996)
struct Edge {
    int to;
    int from;
    int weight;
};
Edge edge[6001];
int dist[501];
int main() {
    int N, M;
 
    bool NegativeCycleExist = false;    // 시작점에서 도달 가능한 타임머신으로 되어있는 사이클이 존재해 가장 빠른 시간이 존재하지 않는 경우
 
    scanf("%d %d", &N, &M);
    for (int i = 0; i <= N; i++)
        dist[i] = 0x07ffffff;            // 무한대 값이라 가정
    for (int i = 0; i < M; i++)
        scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].weight);
    dist[1] = 0;
    for (int i = 0; i < N - 1; i++) {    // N-1번 실행
        for (int j = 0; j < M; j++) {
            if (dist[edge[j].to] > dist[edge[j].from] + edge[j].weight) {
                dist[edge[j].to] = dist[edge[j].from] + edge[j].weight;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        if (dist[edge[i].to] > dist[edge[i].from] + edge[i].weight) {
            NegativeCycleExist = true;
        }
    }
    if (NegativeCycleExist) {
        printf("-1\n");
        return 0;
    }
    for (int i = 2; i <= N; i++) {
        if (dist[i] == 0x07ffffff)
            printf("-1\n");
        else
            printf("%d\n", dist[i]);
    }
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03
[5397번] Keylogger 키로거 - Stack[C++]  (0) 2017.01.02
https://www.acmicpc.net/problem/9935

아이디어는 스택에 문자열을 하나씩 받아오면서 문자열의 끝자리가 폭발 문자열의 끝자리와 같으면

폭발 가능성을 검사한다.

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
#include <iostream>
#include <string>
#include <stdio.h>
 
#pragma warning (disable : 4996)
using namespace std;
 
int main() {
    string str, bomb;
    char stack1[1000001];
    cin >> str >> bomb;
 
    int index = 0;
    int strlen = str.length();
    int bomblen = bomb.length();
 
    for(int i = 0; i < strlen; i++){
        stack1[index++] = str[i];
        if (str[i] == bomb[bomblen - 1]) { //compare
            bool check = false;
            for (int j = bomblen - 1, k = index - 1; j >= 0; j--, k--)
                if (bomb[j] != stack1[k]) {
                    check = true;
                    break;
                }
            if (!check) index -= bomblen;
        }
    }
 
    if (index != 0)
        for (int i = 0; i < index; i++)
            printf("%c", stack1[i]);
    else
        printf("FRULA");
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03
[5397번] Keylogger 키로거 - Stack[C++]  (0) 2017.01.02
[10817번] Three Interger 세 수 - if condition[C++]  (0) 2017.01.02

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


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 <stdio.h>
#include <deque>
 
#pragma warning (disable : 4996)
using namespace std;
 
int main() {
    deque<int> deq;
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        deq.push_back(i);
    printf("<");
    int del;
    while (!deq.empty()) {
        for (int i = 0; i < M; i++) {
            del = deq.front();
            deq.pop_front();
            if (i != M - 1)
                deq.push_back(del);
        }
        if (!deq.empty())
            printf("%d, ", del);
        else
            printf("%d", del);
    }
    printf(">");
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03
[5397번] Keylogger 키로거 - Stack[C++]  (0) 2017.01.02
[10817번] Three Interger 세 수 - if condition[C++]  (0) 2017.01.02
[11721번] Print out per ten lines 열개씩 끊어 출력하기 - For Loop [C++] ☆  (0) 2016.12.29

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


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
#include <iostream>
#include <cstring>
#include <string>
#include <stack>
 
#pragma warning (disable : 4996)
using namespace std;
 
int main() {
    int N;
    string input;
    stack<char> stack1, stack2;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input;
        int size1 = input.size();
        for (int j = 0; j < size1; j++) {
            if (input[j] == '<') {
                if (stack1.empty() == 0){
                    char a;
                    a = stack1.top();
                    stack1.pop();
                    stack2.push(a);
                }
            }
            else if (input[j] == '>') {
                if (stack2.empty() == 0){
                    char a;
                    a = stack2.top();
                    stack2.pop();
                    stack1.push(a);
                }
            }
            else if (input[j] == '-') {
                if (stack1.empty() == 0)
                    stack1.pop();
            }
            else
                stack1.push(input[j]);
        }
 
        if (stack1.size() > 0){
            size1 = stack1.size();
            for (int j = 0; j < size1; j++) {
                char a;
                a = stack1.top();
                stack1.pop();
                stack2.push(a);
            }
        }
 
        int size = stack2.size();
        for (int j = 0; j < size; j++) {
            char a;
            a = stack2.top();
            stack2.pop();
            cout << a;
        }
 
        cout << endl;
    }
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03
[10817번] Three Interger 세 수 - if condition[C++]  (0) 2017.01.02
[11721번] Print out per ten lines 열개씩 끊어 출력하기 - For Loop [C++] ☆  (0) 2016.12.29
[1924번] In 2007 2007년 - For Loop [C++] ☆  (0) 2016.12.28

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


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
#include <iostream>
 
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a > b) {
        if (b >= c)    cout << b;
        else if (b < c) {
            if (a > c) cout << c;
            else if (a < c) cout << a;
            else if (a == c) cout << a;
        }
    }
    else if (a < b) {
        if (a >= c) cout << a;
        else if (a < c) {
            if (b > c) cout << c;
            else if (b < c) cout << b;
            else if (b == c) cout << b;
        }
    }
    else if (a == b) {
        if (a > c) cout << a;
        else if (a < c) cout << a;
        else if (a == c) cout << a;
    }
    return 0;
}
cs

<Amazing Code From cubelover>

1
2
3
4
b,c;main(a){
    for( ; ~scanf("%d",&a) ; a>b? c=b,b=a : a>c?c=a : 0);
    printf("%d",c);
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03
[5397번] Keylogger 키로거 - Stack[C++]  (0) 2017.01.02
[11721번] Print out per ten lines 열개씩 끊어 출력하기 - For Loop [C++] ☆  (0) 2016.12.29
[1924번] In 2007 2007년 - For Loop [C++] ☆  (0) 2016.12.28
[2439번] Star Shooting 2 별찍기2 - For loop [C++]  (0) 2016.12.28

+ Recent posts

티스토리툴바