반응형

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

 

2447번: 별 찍기 - 10

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이

www.acmicpc.net

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
 
using namespace std;
 
char board[6561][6561];
//x, y에서 시작해서 가로 세로의 크기가 각각 n
void solve(int x, int y, int n) {
    if (n == 3) {
        board[x][y] = '*';
        board[x][y+1] = '*';
        board[x][y+2] = '*';
        board[x + 1][y] = '*';
        board[x + 1][y + 1] = ' ';
        board[x + 1][y + 2] = '*';
        board[x + 2][y] = '*';
        board[x + 2][y + 1] = '*';
        board[x + 2][y + 2] = '*';
        return;
    }
    solve(x, y, n / 3);
    solve(x, y + n/3, n / 3);
    solve(x, y + 2*n/3, n / 3);
 
    solve(x + n/3, y, n / 3);
    solve(x + n/3, y + 2*n/3, n / 3);
  
    solve(x + 2*n/3, y, n / 3);
    solve(x + 2*n/3, y + n/3, n / 3);
    solve(x + 2*n/3, y + 2*n/3, n / 3);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    fill(&board[0][0], &board[6560][6561], ' ');
    solve(0, 0, n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j];
        }
        cout << '\n';
    }
 
    
    return 0;
}
 
 cs
반응형
저작자표시

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

[백준 16987번] 계란으로 계란치기  (0) 2021.12.30
[백준 2448번] 별 찍기 - 11  (0) 2021.12.27
[백준 1992번] 쿼드트리  (0) 2021.12.27
[백준 2630번] 색종이 만들기  (0) 2021.12.27
[백준 1780번] 종이의 개수  (0) 2021.12.27
반응형

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

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또

www.acmicpc.net

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
 
using namespace std;
 
char board[64][64];
int res[2];
// x,y에서 시작해서 가로 세로 길이가 각각 n인 영상
void solve(int x, int y, int n) {
    if (n == 1) {
        cout << board[x][y];
        return;
    }
 
    char flag = board[x][y];
    bool run = false;
    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (flag != board[i][j]) run = true;
        }
    }
    if (!run) {
        cout << board[x][y];
        return;
    }
    cout << "(";
    solve(x, y, n / 2);
    solve(x, y + n / 2, n / 2);
    solve(x + n / 2, y, n / 2);
    solve(x + n / 2, y + n / 2, n / 2);
    cout << ")";
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        int s_len = s.length();
        for (int j = 0; j < s_len; j++) {
            board[i][j] = s[j];
        }
    }
    solve(0, 0, n);
 
 
    
    return 0;
}
 
 cs

 

반응형
저작자표시

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

[백준 2448번] 별 찍기 - 11  (0) 2021.12.27
[백준 2447번] 별 찍기 - 10  (0) 2021.12.27
[백준 2630번] 색종이 만들기  (0) 2021.12.27
[백준 1780번] 종이의 개수  (0) 2021.12.27
[백준 1766번] 문제집  (0) 2021.12.20
반응형

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

 

2630번: 색종이 만들기

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

www.acmicpc.net

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
 
using namespace std;
 
int board[128][128];
int res[2];
// x,y에서 시작해서 가로 세로 길이가 각각 n인 종이
void solve(int x, int y, int n) {
    if (n == 1) {
        res[board[x][y]]++;
        return;
    }
    int flag = board[x][y];
    bool run = false;
    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (flag != board[i][j]) run = true;
        }
    }
    if (!run) {
        res[board[x][y]]++;
        return;
    }
    solve(x, y, n / 2);
    solve(x, y + n / 2, n / 2);
    solve(x + n / 2, y, n / 2);
    solve(x + n / 2, y + n / 2, n / 2);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    solve(0, 0, n);
 
    for (int i = 0; i < 2; i++)cout << res[i] << '\n';
 
    
    return 0;
}
 
 cs

 

반응형
저작자표시

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

[백준 2447번] 별 찍기 - 10  (0) 2021.12.27
[백준 1992번] 쿼드트리  (0) 2021.12.27
[백준 1780번] 종이의 개수  (0) 2021.12.27
[백준 1766번] 문제집  (0) 2021.12.20
[뱍쥰 1005번] ACM Craft  (0) 2021.12.20
반응형

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

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수

www.acmicpc.net

 

<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 <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
 
using namespace std;
 
int board[2187][2187];
int res[3];

// x,y에서 시작해서 가로 세로 길이가 각각 n인 종이
void solve(int x, int y, int n) {
    if (n == 1) {
        res[board[x][y] + 1]++;
        return;
    }
    int flag = board[x][y];
    bool run = false;
    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (flag != board[i][j]) run = true;
        }
    }
    if (!run) {
        res[board[x][y] + 1]++;
        return;
    }
    solve(x, y, n / 3);
    solve(x, y + n / 3, n / 3);
    solve(x, y + 2 * n / 3, n / 3);
 
    solve(x + n / 3, y, n / 3);
    solve(x + n / 3, y + n / 3, n / 3);
    solve(x + n / 3, y + 2 * n / 3, n / 3);
 
    solve(x + 2 * n / 3, y, n / 3);
    solve(x + 2 * n / 3, y + n / 3, n / 3);
    solve(x + 2 * n / 3, y + 2 * n / 3, n / 3);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    solve(0, 0, n);
 
    for (int i = 0; i < 3; i++)cout << res[i] << '\n';
 
    
    return 0;
}
 
 cs

 

반응형
저작자표시

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

[백준 1992번] 쿼드트리  (0) 2021.12.27
[백준 2630번] 색종이 만들기  (0) 2021.12.27
[백준 1766번] 문제집  (0) 2021.12.20
[뱍쥰 1005번] ACM Craft  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
반응형

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

 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

<문제 풀이> 위상 정렬, 우선순위 큐

indegree가 0인 정점 중에서 가장 번호가 낮은 정점을 먼저 방문해야 되기 때문에 위상 정렬을 우선순위 큐로 구현하면 됩니다.

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n, m;
vector<int> adj[32001];
int indegree[32001];
 
class cmp {
public:
    bool operator()(int a, int b) {
        return a > b;
    }
};
 
void bfs() {
    priority_queue<int, vector<int>, cmp > pq;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            pq.push(i);
        }
    }
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        cout << u << ' ';
        for (auto& v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                pq.push(v);
            }
            
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b; 
        cin >> a >> b;
        adj[a].push_back(b);
        indegree[b]++;
    }
    bfs();
 
    return 0;
}
 
 cs

 

반응형
저작자표시

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

[백준 2630번] 색종이 만들기  (0) 2021.12.27
[백준 1780번] 종이의 개수  (0) 2021.12.27
[뱍쥰 1005번] ACM Craft  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
반응형

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

 

1005번: ACM Craft

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부

www.acmicpc.net

<문제 풀이> 위상 정렬

 

기본적인 위상 정렬 알고리즘으로 최단거리를 구하면 되는데 주의할 점은

정점 v의 최단거리를 갱신할 때 u -> v에서 u의 건설 시간이 최대가 되는 정점을 택해야 한다.

(u의 모든 정점이 건설이 완료되어야 v를 건설할 수 있으므로 가장 늦게 건설이 완료되는 u를 택함)

dist[v] = max(dist[v], dist[u] + d[v]);

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n, k;
int d[1001];
vector<int> adj[1001];
int indegree[1001];
int dist[1001];
 
void bfs() {
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
            dist[i] = d[i];
        }
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto& v : adj[u]) {
            dist[v] = max(dist[v], dist[u] + d[v]);
            indegree[v]--;
            if (indegree[v] == 0) {
                Q.push(v);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int test_case; cin >> test_case;
    while (test_case--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            indegree[y]++;
        }
        int w; cin >> w;
        bfs();
        cout << dist[w] << '\n';
        fill(dist, dist + 1001, 0);
        fill(indegree, indegree + 1001, 0);
        fill(d, d + 1001, 0);
        for (int i = 0; i < 1001; i++) {
            adj[i].clear();
        }
 
 
    }
 
    return 0;
}
 
 cs
반응형
저작자표시

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

[백준 1780번] 종이의 개수  (0) 2021.12.27
[백준 1766번] 문제집  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 14675번] 단절점과 단절선  (0) 2021.12.19
반응형

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

 

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부

www.acmicpc.net

<문제 풀이> 위상 정렬, 다이나믹 프로그래밍

기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다.

 

indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다.

 

 

위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노드인 2번 정점으로 최단거리를 갱신하면 올바른 답인 24 가 나오지만

 

위와 같은 상황에서는 1번 정점을 고려하지 않기 때문에 24가 아닌 14가 나오게 됩니다.

 

1번 정점과 2번 정점 모두 건설이 완료되어야 3번 정점을 건설할 수 있으므로,

3번 정점을 건설하는데 걸리는 시간은 

(1번 정점과 2번 정점 중 건설이 가장 오래 걸리는 정점의 건설 시간 + 3번 정점의 건설 시간)이 됩니다

=dist[v] = max(dist[v], dist[u] + takeTime[v]);

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n;
vector<int> adj[501];
int indegree[501];
int dist[501];
int takeTime[501];
 
void bfs() {
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
            dist[i] = takeTime[i];
        }
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto& v : adj[u]) {
            dist[v] = max(dist[v], dist[u] + takeTime[v]);
            indegree[v]--;
            if (indegree[v] == 0) {
                Q.push(v);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int v = 1; v <= n; v++) {
        int t;
        cin >> t;
        takeTime[v] = t;
        while (true) {
            int u;
            cin >> u;
            if (u == -1) break;
            
            adj[u].push_back(v);
            indegree[v]++;
        }
    }
    bfs();
   
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << '\n';
    }
    return 0;
}
 
 cs

 

 

반응형
저작자표시

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

[백준 1766번] 문제집  (0) 2021.12.20
[뱍쥰 1005번] ACM Craft  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 14675번] 단절점과 단절선  (0) 2021.12.19
[백준 2661번] 좋은수열  (0) 2021.12.16
반응형

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

 

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부

www.acmicpc.net

<문제 풀이> 위상 정렬, 다이나믹 프로그래밍

기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다.

 

indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다.

 

 

위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노드인 2번 정점으로 최단거리를 갱신하면 올바른 답인 24 가 나오지만

 

위와 같은 상황에서는 1번 정점을 고려하지 않기 때문에 24가 아닌 14가 나오게 됩니다.

 

1번 정점과 2번 정점 모두 건설이 완료되어야 3번 정점을 건설할 수 있으므로,

3번 정점을 건설하는데 걸리는 시간은 

(1번 정점과 2번 정점 중 건설이 가장 오래 걸리는 정점의 건설 시간 + 3번 정점의 건설 시간)이 됩니다

=dist[v] = max(dist[v], dist[u] + takeTime[v]);

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n;
vector<int> adj[501];
int indegree[501];
int dist[501];
int takeTime[501];
 
void bfs() {
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
            dist[i] = takeTime[i];
        }
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto& v : adj[u]) {
            dist[v] = max(dist[v], dist[u] + takeTime[v]);
            indegree[v]--;
            if (indegree[v] == 0) {
                Q.push(v);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int v = 1; v <= n; v++) {
        int t;
        cin >> t;
        takeTime[v] = t;
        while (true) {
            int u;
            cin >> u;
            if (u == -1) break;
            
            adj[u].push_back(v);
            indegree[v]++;
        }
    }
    bfs();
   
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << '\n';
    }
    return 0;
}
 
 cs

 

 

반응형
저작자표시

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

[뱍쥰 1005번] ACM Craft  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 14675번] 단절점과 단절선  (0) 2021.12.19
[백준 2661번] 좋은수열  (0) 2021.12.16
[백준 2132번] 나무 위의 벌레  (0) 2021.12.16

+ Recent posts

티스토리툴바