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

+ Recent posts

티스토리툴바