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

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

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

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

+ Recent posts

티스토리툴바