문제 해설

 

단순히 소수를 구하면 되는 문제로, 우선 소수를 모두 구해주고 해당 범위 내에 있는 소수를 출력해주었습니다.

 

 

코드

 

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 <cstring>
 
using namespace std;
 
bool number[10001];
 
int main() {
 
    int m, n;
 
    cin >> m >> n;
 
    int sum = 0;
    int min = -1;
 
    memset(number, true, sizeof(number));
 
    number[1] = false;
 
    for (int i = 2; i <= n; i++) {
        if (number[i]) {
            for (int j = 2; j <= n / i; j++) {
                number[j * i] = false;
            }
        }
    }
 
    for (int i = m; i <= n; i++) {
        if (number[i]) {
            sum += i;
            if (min == -1) {
                min = i;
            }
        }
    }
 
    if (min == -1) {
        cout << min << '\n';
    }
    else {
        cout << sum << '\n' << min << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

채점 결과

 

 

 

 

문제 출처

 

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

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

4948번: 베르트랑 공준  (0) 2019.04.15
1929번: 소수 구하기  (0) 2019.04.15
17135번: 캐슬 디펜스 (백준 온라인 저지, C++)  (0) 2019.04.08
3184번: 양 (백준 온라인 저지, C++)  (0) 2019.04.05
14225번: 부분수열의 합 (백준 온라인 저지, C++)  (0) 2019.04.04

문제 풀이

 

 문제 해결을 위한 절차는 다음과 같습니다.

1) 궁수의 위치를 정하여 simulation 함수로 넘겨줍니다.

2) 궁수마다 가장 가까운 적의 위치를 중복없이 저장해 줍니다.

3) 사정 거리 내에 들어온다면 적을 없애주고, 적을 한 칸 전진 시킵니다.

4) 남아있는 적이 없다면 simulation을 종료시키고 물리친 적이 가장 많을 때를 저장시켜 줍니다.

 

 

코드

 

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
 
using namespace std;
 
int n, m, d;
int field[15][15];
 
int dist(int ex, int ey, int ay) {
    return abs(n - ex) + abs(ey - ay);
}
 
int simulation(int a, int b, int c) {
    
    int sum = 0;
    int tmp[15][15];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp[i][j] = field[i][j];
        }
    }
 
    while (1) {
        vector<int> v = { a, b, c };
        set<pair<int, int>> s;
 
        for (auto x : v) { //x = a
            
            int dist_f[15][15];
            int dist_min = -1;
 
            memset(dist_f, -1, sizeof(dist_f));
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    
                    if (tmp[i][j] == 1) {
                        dist_f[i][j] = dist(i, j, x);
                        if (dist_min == -1 || dist_min > dist_f[i][j]) {
                            dist_min = dist_f[i][j];
                        }
                    }
                }
            }
 
            if (dist_min <= d) {
 
                int ex = -1, ey = -1;
                for (int j = 0; j < m; j++) {
                    for (int i = 0; i < n; i++) {
                        if (dist_min == dist_f[i][j]) {
                            ex = i;
                            ey = j;
                            break;
                        }
                    }
                    if (ey != -1) {
                        break;
                    }
                }
                s.emplace(ex, ey);
            }
        }
        
        for (auto x : s) {
            tmp[x.first][x.second] = 0;
            sum++;
        }
        
        bool isFin = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                if(i == 0){
                    tmp[i][j] = 0;
                }
                else{
                    tmp[i][j] = tmp[i - 1][j];
                }
                
                if (tmp[i][j] == 1) {
                    isFin = false;
                }
            }
        }
        if (isFin) return sum;
    }
}
 
int main() {
 
    cin >> n >> m >> d;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> field[i][j];
        }
    }
 
    vector<int> p(m, 0);
    p[0] = 1;
    p[1] = 1;
    p[2] = 1;
 
    sort(p.begin(), p.end());
 
    int ans = -1;
    do{
        vector<int> v;
 
        for (int i = 0; i < m; i++) {
            if (p[i] == 1) {
                v.push_back(i);
            }
        }
        int sum = simulation(v[0], v[1], v[2]);
 
        if (ans == -1 || sum > ans) {
            ans = sum;
        }
 
    } while (next_permutation(p.begin(), p.end()));
 
    cout << ans << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1929번: 소수 구하기  (0) 2019.04.15
2581번: 소수 (백준 온라인 저지, C++)  (0) 2019.04.15
3184번: 양 (백준 온라인 저지, C++)  (0) 2019.04.05
14225번: 부분수열의 합 (백준 온라인 저지, C++)  (0) 2019.04.04
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백준 온라인 저지, C++)  (0) 2019.04.04

문제 해설

 

 simulate 함수를 만들어, 같은 울타리 내에 있는 양과 늑대의 수 중 늑대의 수가 양의 수 이상인 경우 양의 수를 0으로 바꾼 후 리턴해주고, 양의 수가 늑대의 수보다 많을 경우 늑대의 수를 0으로 만들어 리턴해 주었습니다. 단순한 bfs 알고리즘을 통해 문제를 풀 수 있습니다.

 

 

코드

 

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 <queue>
using namespace std;
 
int r, c;
string a[250];
bool isVisit[250][250];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
pair<int, int> simulate(int i, int j) {
 
    int s = 0, w = 0;
    queue<pair<int,int>> q;
    if (a[i][j] == 'o') s++;
    if (a[i][j] == 'v') w++;
    isVisit[i][j] = true;
    q.emplace(i, j);
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 0 || nx >= r || ny < 0 || ny >= c || isVisit[nx][ny] == true|| a[nx][ny] == '#') continue;
 
            isVisit[nx][ny] = true;
 
            if (a[nx][ny] == 'o') s++;
            if (a[nx][ny] == 'v') w++;
 
            q.emplace(nx, ny);
        }
    }
 
    if (s > w) w = 0;
    else s = 0;
 
    return make_pair(s, w);
}
 
int main() {
 
    cin >> r >> c;
    memset(isVisit, false, sizeof(isVisit));
 
    for (int i = 0; i < r; i++) {
        cin >> a[i];
    }
    
    int sheep = 0, wolf = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            
            if (isVisit[i][j] == true) continue;
 
            if (a[i][j] == 'o' || a[i][j] == 'v') {
                auto n = simulate(i, j);
                sheep += n.first;
                wolf += n.second;
            }
        }
    }
    cout << sheep << ' ' << wolf << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
 

 

 
제출 결과
 

 

 

문제 출처

 

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

 

3184번: 양

문제 미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다. 마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2581번: 소수 (백준 온라인 저지, C++)  (0) 2019.04.15
17135번: 캐슬 디펜스 (백준 온라인 저지, C++)  (0) 2019.04.08
14225번: 부분수열의 합 (백준 온라인 저지, C++)  (0) 2019.04.04
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백준 온라인 저지, C++)  (0) 2019.04.04
14502번: 연구소 (백준 온라인 저지, C++)  (0) 2019.04.03

문제 해설

 

가능한 부분 수열의 합을 모두 벡터에 넣어주고 벡터를 정렬한 후 unique함수를 활용하여 중복을 배열의 가장 뒤로 보내주었습니다. 이후 인덱스를 비교하여 가장 작은 자연수를 출력시켜 주었습니다.

 

 

코드

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
 
    int n;
    int d[20];
    cin >> n;
    vector <int> v;
 
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
 
    v.push_back(0);
    v.push_back(d[0]);
 
    for (int i = 1; i < n; i++) {
        int x = v.size();
        for (int j = 0; j < x; j++) {
            v.push_back(v[j] + d[i]);
        }
    }
 
    sort(v.begin(), v.end());
    unique(v.begin(), v.end());
 
 
    for(int i = 1; i <= v.size(); i++){
        if (i == v.size()) {
            cout << i << '\n';
        }
        else if(v[i] != i){
            cout << i << '\n';
            break;
        }
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

14225번: 부분수열의 합

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

17135번: 캐슬 디펜스 (백준 온라인 저지, C++)  (0) 2019.04.08
3184번: 양 (백준 온라인 저지, C++)  (0) 2019.04.05
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백준 온라인 저지, C++)  (0) 2019.04.04
14502번: 연구소 (백준 온라인 저지, C++)  (0) 2019.04.03
14500번: 테트로미노 (백준 온라인 저지, C++)  (0) 2019.04.03

문제 풀이

 

 bool 타입의 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
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, m;
    int ans = 0;
    bool com[201][201];
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            com[i][j] = false;
        }
    }
 
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        com[x][y] = true;
        com[y][x] = true;
    }
 
    for (int i = 1; i <= n - 2; i++) {
        for (int j = i + 1; j <= n - 1; j++) {
            if (com[i][j]) continue;
            for (int k = j + 1; k <= n; k++) {
                if (com[i][k] || com[j][k]) continue;
                ans++;
            }
        }
    }
    cout << ans << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

문제 출처

 

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

 

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다. 입력 첫째 줄에 정수 N과 M이 주어진다. N은

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

3184번: 양 (백준 온라인 저지, C++)  (0) 2019.04.05
14225번: 부분수열의 합 (백준 온라인 저지, C++)  (0) 2019.04.04
14502번: 연구소 (백준 온라인 저지, C++)  (0) 2019.04.03
14500번: 테트로미노 (백준 온라인 저지, C++)  (0) 2019.04.03
2448번: 별 찍기 - 11 (백준 온라인 저지, C++)  (0) 2019.04.02

문제 풀이

 

 이 문제는 바이러스가 퍼지는 부분은 단순한 bfs 문제로 풀이가 가능했지만, 벽을 세우는 부분에서 코드가 길어지다 보니 헷갈리는 부분이 생겼던 문제입니다. 코드를 최대한 단순하게 짜는 것이 실수를 줄이는 방법이 될 것 같습니다..

 

 

코드

 

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
#include <iostream>
#include <queue>
 
using namespace std;
 
int n, m;
int room[8][8];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int bfs(queue<pair<int, int>> q) {
    
    int space = 0;
    int d[8][8] = { 0, };
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            d[i][j] = room[i][j];
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (d[nx][ny] == 0)
            {
                d[nx][ny] = 2;
                q.push(make_pair(nx, ny));
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (d[i][j] == 0)
                space++;
        }
    }
    return space;
}
 
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int ans = 0;
    queue<pair<int, int>> q;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> room[i][j];
            if (room[i][j] == 2)
                q.push(make_pair(i, j));
        }
    }
    for (int i1 = 0; i1 < n; i1++)
    {
        for (int j1 = 0; j1 < m; j1++)
        {
            if (room[i1][j1] != 0) continue;
            for (int i2 = 0; i2 < n; i2++)
            {
                for (int j2 = 0; j2 < m; j2++)
                {
                    if (room[i2][j2] != 0) continue;
                    for (int i3 = 0; i3 < n; i3++)
                    {
                        for (int j3 = 0; j3 < m; j3++)
                        {
                            if (room[i3][j3] != 0) continue;
                            if (i1 == i2 && j1 == j2)
                                continue;
                            if (i2 == i3 && j2 == j3)
                                continue;
                            if (i1 == i3 && j1 == j3)
                                continue;
 
                            room[i1][j1] = 1;
                            room[i2][j2] = 1;
                            room[i3][j3] = 1;
 
                            int x = bfs(q);
                            if (x > ans)
                                ans = x;
 
                            room[i1][j1] = 0;
                            room[i2][j2] = 0;
                            room[i3][j3] = 0;
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.  일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

14225번: 부분수열의 합 (백준 온라인 저지, C++)  (0) 2019.04.04
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백준 온라인 저지, C++)  (0) 2019.04.04
14500번: 테트로미노 (백준 온라인 저지, C++)  (0) 2019.04.03
2448번: 별 찍기 - 11 (백준 온라인 저지, C++)  (0) 2019.04.02
1978번: 소수 찾기 (백준 온라인 저지, C++)  (0) 2019.04.02

문제 풀이

 

 여기서 중요한 부분은 'ㅗ, ㅓ, ㅏ, ㅜ' 모양의 테트로미노를 해결하는 것입니다. 따라서 이를 for문으로 예외 처리 해주었습니다. 이외의 테트로미노는 한 번에 처리가 가능하기 때문에 함수로 선언하여 문제를 풀었습니다.

 

 

코드

 

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
#include <iostream>
 
using namespace std;
 
int n, m;
int ans;
int board[500][500];
bool isVisit[500][500];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
void ttr(int x, int y, int sum, int cnt) {
 
    if (cnt == 4)
    {
        if (sum > ans)
            ans = sum;
        return;
    }
 
    if (isVisit[x][y] == true) return;
    
    if (x < 0 || x >= n || y < 0 || y >= m) return;
 
    isVisit[x][y] = true;
    
    for (int i = 0; i < 4; i++)
        ttr(x + dx[i], y + dy[i], sum + board[x][y], cnt + 1);
    
    isVisit[x][y] = false;
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    ans = 0;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ttr(i, j, 0, 0);
        
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < m - 2; j++)
        {
            int sum = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i - 1][j + 1];
            if (sum > ans)
                ans = sum;
        }
    }
    for (int i = 1; i < n - 1; i++)
    {
        for (int j = 0; j < m - 1; j++)
        {
            int sum = board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i - 1][j + 1];
            if (sum > ans)
                ans = sum;
        }
    }
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < m - 2; j++)
        {
            int sum = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1];
            if (sum > ans)
                ans = sum;
        }
    }
    for (int i = 0; i < n - 2; i++)
    {
        for (int j = 0; j < m - 1; j++)
        {
            int sum = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1];
            if (sum > ans)
                ans = sum;
        }
    }
    cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 꼭짓점끼리 연결되어 있어야 한다. 즉, 변과 꼭짓점이 맞닿아있으면 안된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백준 온라인 저지, C++)  (0) 2019.04.04
14502번: 연구소 (백준 온라인 저지, C++)  (0) 2019.04.03
2448번: 별 찍기 - 11 (백준 온라인 저지, C++)  (0) 2019.04.02
1978번: 소수 찾기 (백준 온라인 저지, C++)  (0) 2019.04.02
2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02

문제 해설

 

 현재 높이의 2배의 삼각형이 다음에 만들어진다는 것에서 착안하여 문제를 풀었습니다.

 

 

 즉, 위의 그림과 같은 규칙으로 삼각형이 생성됩니다. 따라서 이를 코드로 구현하면 아래와 같습니다.

(+ null 문자열이 출력되지 않도록 유의합니다.)

 

 

코드

 

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>
 
using namespace std;
 
char d[3072][6144];
 
void star(int n) {
 
    for (int i = n / 2; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            d[i][j] = d[i - n / 2][j];
    }
 
    for (int i = n / 2; i < n; i++)
    {
        for (int j = n; j < 2 * n; j++)
            d[i][j] = d[i][j - n];
    }
 
    for (int i = 0; i < n / 2; i++)
    {
        for (int j = (2 * n) - (n / 2) - 1; j >= n / 2; j--)
        {
            d[i][j] = d[i][j - (n / 2)];
            d[i][j - (n / 2)] = ' ';
        }
    }
    return;
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 2 * n; j++)
            d[i][j] = ' ';
    }
 
    //initial triangle
    d[0][2] = '*';
    d[1][1] = '*';
    d[1][3] = '*';
    for (int i = 0; i < 5; i++)
        d[2][i] = '*';
 
    for (int i = 3; i <= n; i *= 2)
    {
        if (i == 3)
            continue;
        else
            star(i);
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 2 * n; j++)
            cout << d[i][j];
        cout << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

2448번: 별 찍기 - 11

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10)

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

14502번: 연구소 (백준 온라인 저지, C++)  (0) 2019.04.03
14500번: 테트로미노 (백준 온라인 저지, C++)  (0) 2019.04.03
1978번: 소수 찾기 (백준 온라인 저지, C++)  (0) 2019.04.02
2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02
1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01

+ Recent posts

티스토리툴바