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



CCW를 활용하여 면적을 구하는 문제이다.


여러개의 좌표가 주어질 때, CCW를 활용해서 면적을 구하는 방법에도 여러가지가 있다.



필자가 구현한 것처럼, 다각형을 이루는 점 하나를 중심으로 CCW를 돌리는 방법이 있고,


원점과 같은 다각형 외부의 정점을 잡아서 CCW를 수행하는 방법이 있다.


CCW 함수가 시행되는 횟수의 차이가 있을 것이다.



이 문제에서 또 유의할 것은, 어떤 자료형을 사용할 것이냐이다. n이 10만을 넘어가기 때문에, 면적을 구하는 과정에서 int 범위 밖으로 나갈 수 있다.


따라서 long long을 사용해주면 되겠다.



면적을 구하는 중간에 음수가 나오더라도, 계산 중간중간에 나오는 양수들 때문에 알아서 절댓값은 넓이만큼 구해지게 된다. 따라서 결과에서만 절댓값을 취하고, 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<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
}p[10001];
int n;
 
ll ccw(POT p1, POT p2, POT p3) {
    ll ret;
    ret = (p1.x*p2.y + p2.x*p3.y + p3.x* p1.y) - 
        (p1.y*p2.x + p2.y*p3.x + p3.y* p1.x);
    return ret;
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}
cs



기준벡터를 원점으로 평행이동 시켜서



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
//좌표값 정수
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
}p[10001];
 
int n;
ll ccw(POT p1, POT p2) {
    return p1.x*p2.y - p1.y*p2.x;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
 
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> p[i].x >> p[i].y;
    ll Sum = 0;
    for (int i = 0; i < n-1; i++)
        Sum += ccw(p[0], p[i], p[i + 1]);
    printf("%.1lf", abs(Sum / 2.0));
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 6439 교차 C++  (0) 2019.08.11
백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10

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



CCW 알고리즘을 그대로 구현해주면 된다.


p1 p2 p3가 있을 때, 순서대로 선분을 만들면 선분 p1p2, 선분 p2p3가 생긴다.


나중에 생긴 선분 p2p3가 선분 p1p2에 대해서 어떻게 위치하고 있는지 생각해보면 된다.


p2를 p1으로 평행이동해서 벡터를 생각해본다면 이해가 좀 더 쉽다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//좌표값 정수
#include<iostream>
using namespace std;
typedef long long ll;
struct POT {
    int x, y;
};
int ccw(POT p1, POT p2, POT p3) {
    ll ret;
    ret = (p1.x*p2.y + p2.x*p3.y + p3.x* p1.y) - 
        (p1.y*p2.x + p2.y*p3.x + p3.y* p1.x);
    if (ret < 0) return -1;
    else if (ret == 0) return 0;
    else return 1;
}
int main(void) {
    POT p1, p2, p3;
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;
    cout << ccw(p1, p2, p3);
    return 0;
}
cs






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
 
using namespace std;
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) > 0) return 1;
    else if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) < 0) return -1;
    else
        return 0;
}
 
int main(void) {
 
    int x1, y1, x2, y2, x3, y3;
 
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
 
    cout << ccw(x1, y1, x2, y2, x3, y3) << '\n';
    
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2162: 선분 그룹 C++  (0) 2019.08.11
백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09

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



오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.



우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.


따라서 자리번호를 매겼다.


그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 4개 이상 포함한다면 카운트를 해주었다.


순서가 구분이 안 되서 생기는 문제는, 자리번호를 조합으로 뽑으면 순서에 상관없이 하나만 뽑히기 때문에 해결된다.



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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<string>
#include<queue>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int seat[6][6];
bool isused[25];
int st = 0, arr[8], dis[6][6], map[6][6];
queue<pair<int, int> > q;
int res = 0;
bool endFlag = false;
 
void process() {
    int idx = 0;
    endFlag = false;
    for (int i = 0; i < 5; i++) { //뽑힌 학생의 자리번호 1로
        for (int j = 0; j < 5; j++) {
            if (seat[i][j] == arr[idx]) {
                map[i][j] = 1;
                idx++;
                //if (idx == 7) return; 이 구문 때문에 아래 카운트가 안먹혀서 시간낭비
            }
        }
    }
 
    int sCnt = 0;
    //소영 카운트
    for (int i = 0; i < 5; i++) 
        for (int j = 0; j < 5; j++) 
            if (map[i][j] == 1 && m[i][j] == 'S') sCnt++;
        
    
    if (sCnt < 4) endFlag = true;
}
void init() {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            map[i][j] = 0; //자리번호 배열 초기화
            dis[i][j] = -1; //방문처리 배열
        }
    
}
 
void bfs(pair<int, int> start) {
    q.push(start);
    dis[start.first][start.second]++;
    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
            if (dis[nr][nc] >= 0 || map[nr][nc] != 1) continue;
            q.push({ nr, nc });
            cnt++;
            dis[nr][nc] = cnt;
        }
    }
    
    if (cnt == 6) //7명이 붙어 앉은 경우
        res++;
    
}
 
void pick(int k) {
    if (k == 7) { //1. 자리번호 7개 선택
    
        init(); 
 
        process();
        if (endFlag) return;
 
        for (int i = 0; i < 5; i++) 
            for (int j = 0; j < 5; j++) 
                if (map[i][j] == 1 && dis[i][j] < 0) 
                    bfs({ i, j }); 
        
        return;
    }
    
    if (k == 0) st = 0;
    for (int i = st; i < 25; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            pick(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int cnt = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            cin >> m[i][j];
            seat[i][j] = cnt;
            cnt++;
        }
    
    pick(0);
    cout << res;
    return 0;
}
 
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09

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


4방향 dfs 탐색을 활용해서 y가 네개 이하인 경우에만 결과에 포함시키려고 했다.


이렇게 접근하면 자리에 앉아 있는 사람이 y파인지s파인지 말고는 개별적으로 구분할 수 없기 때문에 각자 결과로 나온 문자열을 구분하지 못한다.


가령 sysysys라는 문자열은 맞는 결과이지만, 행렬에서 어떤 위치의 성분을 가져다가 저걸 만들어냈느냐에 따라서 서로 다른 문자열일 수도 있고 같은 문자열일 수도 있다.



아래는 틀린 코드이다.



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
#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
vector<pair<int, int> > v;
set<vector<pair<int, int> > > pos;
set<string> ans;
void dfs(int k, int row, int col, string mem, int ycnt) {
    if (k == 7) {
        cout << mem << '\n';
        cout << "하나\n";
        //ans.insert(mem);
        
        return;
    }
    cout << mem << '\n';
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
        if (m[nr][nc] == 'Y' && ycnt >= 3) continue;
        
 
 
        if (m[nr][nc] == 'Y') dfs(k + 1, nr, nc, mem + m[nr][nc], ycnt + 1);
        else
            dfs(k + 1, nr, nc, mem + m[nr][nc], ycnt );
    }
    
}
 
int main(void) {
    
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> m[i][j];
 
    string tmp = "";
    
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            int ycnt = 0;
            if (m[i][j] == 'Y') ycnt++;
            dfs(1, i, j, tmp+m[i][j], ycnt);
        }
    //cout << *ans.begin();
    return 0;
}
 
cs


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

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

연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1799번: 비숍 (C++)  (0) 2019.07.24
백준 1759번: 암호 만들기 (C++)  (0) 2019.07.23
[오답] 백준 9663번: N-Queen (C++)  (0) 2019.07.21

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



자리수가 추가될 때마다 현재 상태의 수가 소수인지 아닌지를 판별해주면 된다.


가령 7331을 만들기 위해서, 처음에 7을 골라서 확인하고, 73을 확인하고, 733을 확인하고 ... 이런 흐름이다.


처음에 2를 고르고, 다음에 21이 나왔을텐데, 21은 소수가 아니기 때문에 21#$!@#는 더이상 확인할 필요가 없는 것이다.



신경써줄 부분은, 소수 판별 함수에서 1은 바로 소수가 아님을 반환하는 것과, 가장 큰 자리의 수가 0이 되지 않도록 해주는 부분이다.




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<vector>
using namespace std;
int n, arr[10], st = 0;
bool isPrime(int val) {
    if (val == 1) return false; //1은 소수가 아님
    for (int i = 2; i*i <= val; i++)
        if (val % i == 0) return false;
    return true;
}
void backTracking(int k, int num) {
    
    //소수검사
    if (k != 0) 
        if (!isPrime(num)) return;
    
    if (k == n) {
        cout << num << '\n';
        return;
    }
 
    //가장 큰 자리수로 0못오게
    if (k == 0)st = 1;
    else
        st = 0;
 
    for (int i = st; i <= 9; i++) 
        backTracking(k + 1, num * 10 + i);
}
int main(void) {
    cin >> n;
    backTracking(0,0);
    
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09

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



1,2,3 세개의 숫자를 활용해서 길이 n의 수열을 만들면 된다.


기본적으로 여기까지는 백트래킹을 활용해서 진행해주면 된다.


이후에 나쁜 수열을 걸러내는 과정에서 substr을 적절히 활용해주면 되겠다.


주의할 점은, 검사를 재귀의 진입 부분에서 해야 한다는 것이다.



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
#include<iostream>
#include<set>
#include<string>
using namespace std;
int n, a[3] = { 1,2,3 }, arr[81];
string str = "";
set<string> ans;
bool ef = false;
void backTracking(int k) {
 
    str = "";
    for (int i = 0; i < k; i++)
        str += (arr[i] + '0');
    
    //부분 수열 존재 검사
    for (int i = 1; i <= k / 2; i++) { //수열 길이 절반까지만 확인하면 됨
        for (int j = 0; j <= k - 2 * i; j++) {
            if (str.substr(j, i) == str.substr(j + i, i)) {
                return;
            }
        }
    }
 
    //길이 n 완성
    if (k == n) {
        for (int i = 0; i < k; i++)
            cout << arr[i];
        exit(0); //가장 먼저 나오는 게 제일 작은 수열
        return;
    }
 
    for (int i = 0; i < 3; i++) {
        arr[k] = a[i];
        backTracking(k + 1);
        if (ef) return;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    backTracking(0);
 
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09

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


5 * 5의 격자판이 주어진다.


그 격자판에 있는 정수들을 활용해서 길이 6의 수열을 만들어야 한다.


이 때 사용했던 숫자라도 중복해서 사용할 수 있다.


또한, 숫자는 직전에 선택했던 숫자의 동서남북 방향에 위치한 숫자중에 하나로 선택해야 한다.



중복 제거를 간편하게 하기 위해서 set을 사용했다.



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
#include<iostream>
#include<set>
#include<string>
using namespace std;
int m[6][6];
string str = "";
set<int> res;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int depth, int row, int col, int cur) {
    if (depth == 5) { //depth가 0일때 이미 처음게 골라져있는 상태임
        res.insert(cur);
        
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
        dfs(depth + 1, nr, nc, cur * 10 + m[nr][nc]);
    }
}
 
int main(void) {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> m[i][j];
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            dfs(0, i, j, m[i][j]);
        }
    }
 
    cout << res.size();
 
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09

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

 

2589번: 보물섬

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지

www.acmicpc.net

육지가 될 수 있는 땅 한 칸 한 칸에 대해 개별적으로 bfs를 수행해주면 된다.

 

방문처리를 거리 측정으로 하면서 최댓값을 구해주면 된다.

 

 

 

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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09

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


간단한 DP 문제이다.


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
//1-indexed
#include<iostream>
 
using namespace std;
typedef long long ll;
ll m[33][33], d[33][33][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17070번: 파이프 옮기기 1 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07

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


삼성 상시 검정 A형 기출 문제이다. 삼성의 문제이니만큼 완전탐색 혹은 시뮬레이션 문제일 것이다.


하지만 이를 생각하더라도, 동적계획법을 통해서 너무 쉬운 풀이가 가능하기 때문에 DP를 활용해서 간단하게 풀었다.


정점 i,j에 도착할 때, 어떤 방향 상태를 가지고 도착하는지 생각해보면, 세가지가 가능함을 알 수 있다.


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
//1-indexed
#include<iostream>
 
using namespace std;
int m[18][18], d[18][18][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}
cs


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

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2589번: 보물섬 (C++)  (0) 2019.08.09
백준 17069번: 파이프 옮기기 2 (C++)  (0) 2019.08.09
백준 14890번: 경사로 (C++)  (0) 2019.08.09
백준 14889번: 스타트와 링크 (C++)  (0) 2019.08.07
백준 14891번: 톱니바퀴 (C++)  (0) 2019.08.07

+ Recent posts

티스토리툴바