swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB&categoryId=AV7GLXqKAWYDFAXB&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 농장을 입력받는다.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <stdio.h>
#include <string.h>
 
using namespace std;
 
int N;
int map[49][49];
int answer;
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        memset(map, 0, sizeof(map));
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                scanf_s("%1d", &map[i][j]);
            }
        }
 
        //해법
        /*
        위 삼각형, 아래 삼각형 나누어서 계산(마름모 별찍기 응용 문제)
        */
        for (int i = 0; i < N / 2; i++) {
            for (int j = N / 2 - i; j <= N / 2 + i; j++) {
                answer += map[i][j];
            }
        }
        for (int i = 0; i <= N / 2; i++) {
            for (int j = i; j < N - i; j++) {
                answer += map[i + N / 2][j];
            }
        }
 
        //결과 출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    
    //종료
    return 0;
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 3752 - 가능한 시험 점수  (0) 2021.01.13
[C++] SWEA 2814 - 최장 경로  (0) 2021.01.12
[C++] SWEA 2817 - 부분 수열의 합  (0) 2021.01.08
[C++] SWEA 1215 - 회문1  (0) 2021.01.05
[C++] SWEA 1208 - Flattern  (0) 2021.01.02

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 주어진 수열의 각 원소를 모든 경우에 따라 더해본다.

2. 원소들의 합이 K인 경우의 수를 출력한다.

 

<해법>

가장 기본적인 브루트 포스 문제라고 생각합니다. 원소를 고를 때 중복을 제거하는 방식을 고려하여 구현하였습니다.

 

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>
 
using namespace std;
 
int N, K;
int arr[20];
int answer;
 
void makeSum(int idx, int sum) {
 
    //합이 K를 넘는 경우 -> 더 이상 더할 필요없으므로 종료
    if (sum > K) {
        return;
    }
 
    //합이 K인 경우 -> answer갱신 후 종료
    if (sum == K) {
        answer++;
        return;
    }
 
    //자신보다 뒤에 있는 원소 더해보기(중복 제거 위해)
    for (int i = idx; i < N; i++) {
        makeSum(i + 1, sum + arr[i]);
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, K = 0;
        answer = 0;
 
        //입력
        cin >> N >> K;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
 
        //해법
        /*
        모든 원소 다 더해보기
        */
        makeSum(0, 0);
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 2814 - 최장 경로  (0) 2021.01.12
[C++] SWEA 2805 - 농작물 수확하기  (0) 2021.01.08
[C++] SWEA 1215 - 회문1  (0) 2021.01.05
[C++] SWEA 1208 - Flattern  (0) 2021.01.02
[C++] SWEA 1244 - 최대 상금  (0) 2020.12.31

www.algospot.com/judge/problem/read/BOARDCOVER

 

algospot.com :: BOARDCOVER

게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이

www.algospot.com

<풀이>

1. 보드를 입력받는다.

2. 해당 보드를 제시된 블록들로 채울 수 있는 모든 경우의 수를 출력한다.

 

<해법>

1. 블록을 채우는 방법

=> 보드를 탐색해 나가면서 가장 처음 흰색('.')이 나올 때, 이 부분을 블록으로 채워줘야 합니다. 이 때, 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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <string>
#include <string.h>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
int H, W;
char map[20][20];
int answer;
 
//4개 블록의 좌표
pos block[4][3] = {
    {{0,0}, {0,1}, {1,0}},  //①
    {{0,0}, {1,0}, {1,-1}}, //②
    {{0,0}, {1,0}, {1,1}},  //③
    {{0,0}, {0,1}, {1,1}}   //④
};
 
int countWhite() {
    int count = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '.') {
                count++;
            }
        }
    }
    return count;
}
 
pos firstWhitePos() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '.') {
                return { i, j };
            }
        }
    }
}
 
bool isTypeAble(pos p, int type) {
 
    for (int i = 0; i < 3; i++) {
        int x = p.x + block[type][i].x;
        int y = p.y + block[type][i].y;
 
        if (x < 0 || y < 0 || x >= H || y >= W) {
            return false;
        }
 
        if (map[x][y] == '#') {
            return false;
        }
    }
 
    return true;
 
}
 
void colorBoard(pos p, int type, char color) {
 
    for (int i = 0; i < 3; i++) {
        int x = p.x + block[type][i].x;
        int y = p.y + block[type][i].y;
 
        map[x][y] = color;
    }
 
}
 
void boardCover(int remainCnt) {
    
    //종료 조건 : 블록을 모두 놓은 경우
    if (remainCnt == 0) {
        answer++;
        return;
    }
 
    //칠해할 흰색 부분(가장 첫 번째 등장한 흰색)
    pos cur = firstWhitePos();
 
    //4개의 블록 타입 모두 넣어보기
    for (int type = 0; type < 4; type++) {
 
        //타입을 칠할 수 있다면
        if (isTypeAble(cur, type)) {
            
            //검정색으로 칠하기
            colorBoard(cur, type, '#');
 
            //재귀 호출
            boardCover(remainCnt - 1);
 
            //흰색으로 다시 칠하기
            colorBoard(cur, type, '.');
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        H = 0, W = 0;
        memset(map, '#', sizeof(map));
        answer = 0;
 
        //입력
        cin >> H >> W;
        for (int i = 0; i < H; i++) {
            string tmp;
            cin >> tmp;
            for (int j = 0; j < W; j++) {
                map[i][j] = tmp[j];
            }
        }
 
        //해법
        /*
        모두 검정색으로 채워져 있는 경우 or 흰색 개수 3의 배수 아닌 경우 -> 탐색X
        나머지 경우는 블록을 모두 놓아본다
        */
        if (countWhite() != 0 && countWhite() % 3 == 0) {
            boardCover(countWhite() / 3);
        }
 
        //결과 출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

브루트포스와 구현에 대해 알아볼 수 있는 문제였습니다.

위 문제에서 구현이 어렵다고 생각되시면, 아래 문제를 먼저 풀어보시는 것도 도움이 될 것 같습니다!

www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

 

저작자표시

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

[C++] Algospot - 쿼드 트리 뒤집기(QUADTREE)  (0) 2021.01.13
[C++] Algospot - 시계 맞추기(CLOCKSYNC)  (0) 2021.01.11
[C++] Algospot - 소풍(PICNIC)  (0) 2021.01.06

programmers.co.kr/learn/courses/30/lessons/17679

 

코딩테스트 연습 - [1차] 프렌즈4블록

프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙

programmers.co.kr

<풀이>

1. 주어진 보드에서 지워질 4개의 블록을 모두 지운다.

2. 지워진 블록 위에있는 블록들을 아래로 내린다.

3. 더 이상 블록을 지울 수 없을 때 까지 반복한다.

4. 지워진 블록 개수를 반환한다

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않습니다. 문제에서 주어진 대로 정확하게 구현하는게 핵심입니다.

 

① 주어진 보드에서 지워질 4개의 블록들을 모두 찾는다.

: 바로 지우면 안됩니다. 블록을 중복해서 찾아야하기 때문입니다. 저는 지워질 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
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
int M, N;
vector<string> map;
 
//x, y좌표에서 지울 수 있는 4블록인지 확인
bool is_4Block(int x, int y, char c) {
 
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            if (map[x + i][y + j] != c) {
                return false;
            }
        }
    }
    return true;
}
 
//블록 내리기
void blockDown() {
 
    for (int i = M - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
 
            //빈 칸 탐색
            if (map[i][j] == '#') {
 
                //빈 칸위에 블록이 있는지 탐색
                for (int k = i; k >= 0; k--) {
 
                    //빈 칸 위에 있는 가장 가까운 블록하나 내리기
                    if (map[k][j] != '#') {
                        map[i][j] = map[k][j];
                        map[k][j] = '#';
                        break;
                    }
                }
            }
        }
    }
}
 
//지워진 블록 세기
int countRemoveBlock() {
 
    int count = 0;
 
    //빈 칸 개수 세기
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == '#') {
                count++;
            }
        }
    }
 
    return count;
}
 
int solution(int m, int n, vector<string> board) {
 
    int answer = 0;
 
    //초기화(전역 변수로 사용하기 위해)
    M = m, N = n;
    map = board;
 
    //해법
    while (true) {
 
        //지울 블록의 좌표를 담는 벡터
        vector<pos> removeBlock;
 
        //지울 블록 정하기
        for (int i = 0; i < M - 1; i++) {
            for (int j = 0; j < N - 1; j++) {
 
                //빈 칸이 아니고, 4블록을 지울 수 있는 경우
                if (map[i][j] != '#' && is_4Block(i, j, map[i][j])) {
                    
                    //지울 블록 4개의 좌표를 벡터에 담는다
                    removeBlock.push_back({ i, j });
                    removeBlock.push_back({ i, j + 1 });
                    removeBlock.push_back({ i + 1, j });
                    removeBlock.push_back({ i + 1, j + 1 });
                }
            }
        }
 
        //종료 조건 : 지울 블록이 없는 경우
        if (removeBlock.empty()) {
            break;
        }
 
        //블록 지우기
        for (int i = 0; i < removeBlock.size(); i++) {
            int x = removeBlock[i].x;
            int y = removeBlock[i].y;
 
            map[x][y] = '#';
        }
 
        //블록 내리기
        blockDown();
    }
 
    //결과 계산
    answer = countRemoveBlock();
 
    //결과 반환
    return answer;
}
 
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11
[C++] 프로그래머스 - 셔틀버스  (0) 2021.01.04
[C++] 프로그래머스 - 뉴스 클러스터링  (0) 2021.01.01
[C++] 프로그래머스 - 추석 트래픽  (0) 2020.12.29

www.algospot.com/judge/problem/read/PICNIC

 

algospot.com :: PICNIC

소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로

www.algospot.com

<풀이>

1. 학생 수와 친구 정보를 입력받는다.

2. 모든 학생의 짝을 지으면서, 서로 친구인지 확인한다.

3. 짝이 모두 지어진 경우의 개수를 출력한다.

 

<해법>

1. 모든 학생의 짝을 지을 때, 중복을 처리하는 방법

=> 모든 학생의 짝을 지을 때, 다음과 같은 중복들이 있습니다. 학생 수는 6명이라고 가정하겠습니다.

 

첫 번째는, (0 1), (2 3), (4 5)로 짝을 짓고, (1 0), (3 2), (5 4)로 또 짝을 짓는 경우입니다. 친구끼리 순서는 상관이 없기 때문에 중복됩니다. 

두 번째는, (0 1), (2 3), (4 5)로 짝을 짓고, (2 3), (4 5), (0 1)로 또 짝을 짓는 경우입니다. 짝끼리 순서는 상관이 없기 때문에 중복됩니다.

 

저는 이 문제를 풀기 전에, '수학적으로 어떻게 풀었지?'를 먼저 생각하였습니다.

'짝 개수를 찾는 경우의 수를 어떻게 구했더라?'

 

(6C2 x 4C2 x 2C2) / 3! 이었습니다.

 

위 수식에서 중복의 힌트를 얻었습니다. 

6C2에서 C는 첫 번째 중복의 경우를 제거합니다. 친구끼리 순서는 상관이 없으므로, C(조합)을 사용합니다.

3!은 두 번째 중복의 경우를 제거합니다. 짝 끼리 순서는 상관이 없으므로, 3개의 짝을 세우는 순서(3!)로 나눕니다.

 

그렇다면 코드로 두 개의 중복을 어떻게 제거해야 할까요?

 

첫 번째 중복의 제거는 '앞의 친구가 무조건 숫자가 더 작다'의 로직을 사용합니다. (0 1)은 가능하지만 (1 0)은 불가능하게 만드는 것입니다.

두 번째 중복의 제거는 '앞 짝의 첫 번째 친구의 숫자가 더 작다'의 로직을 사용합니다. (0 1), (2 3)은 가능하지만 (2 3), (0 1)은 불가능하게 만드는 것입니다.

 

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
#include <iostream>
#include <string.h>
 
using namespace std;
 
int n, m;
bool areFriendsMap[10][10];
bool visited[10];
int answer;
 
//모든 친구쌍 만들어 보기
void makeFriends(int pairCnt) {
 
    //종료조건 : 친구쌍을 모두 만들었을 경우
    if (pairCnt == n / 2) {
        answer++;
        return;
    }
 
    //짝을 찾아야할 다음 친구 찾기(번호가 가장 작은 친구) -> 분모의 3! 부분
    int firstPerson = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            firstPerson = i;
            break;
        }
    }
 
    //친구의 짝 찾기 -> 6C2, 4C2, 2C2의 C(조합) 부분
    for (int i = firstPerson + 1; i < n; i++) {
 
        //짝이 없고, 둘이 친구인 경우 -> 짝 만들기
        if (!visited[i] && areFriendsMap[firstPerson][i]) {
 
            visited[firstPerson] = true, visited[i] = true;
 
            makeFriends(pairCnt + 1);
 
            visited[firstPerson] = false, visited[i] = false;        
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
        
        //초기화
        n = 0; m = 0;
        memset(areFriendsMap, false, sizeof(areFriendsMap));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            areFriendsMap[a][b] = true; areFriendsMap[b][a] = true;
        }
 
        //해법
        /*
        가능한 친구쌍 모두 만들어보기
        */
        makeFriends(0);
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] Algospot - 쿼드 트리 뒤집기(QUADTREE)  (0) 2021.01.13
[C++] Algospot - 시계 맞추기(CLOCKSYNC)  (0) 2021.01.11
[C++] Algospot - 게임판 덮기(BOARDCOVER)  (0) 2021.01.07

www.acmicpc.net/problem/1018

 

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

<풀이>

1. 보드를 입력받는다.

2. 해당 보드에서 8x8 사이즈로 만들 수 있는 체스판 중, 색칠해야하는 최소 개수를 출력한다.

 

<해법>

모든 경우를 다 해보아야 합니다. 8x8 사이즈의 판을 탐색하면서, 해당 판에서 B 또는 W로 모두 칠해보고 최소값을 갱신합니다.

 

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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int N, M;
vector<string> map;
int answer;
 
//왼쪽 위가 B인 체스판
string Bchess[] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
};
 
//왼쪽 위가 W인 체스판
string Wchess[] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};
 
//해당 좌표에서 칠하는 페인트의 최소 개수
int minPaintCount(int x, int y) {
 
    //왼쪽 위가 B인 체스판으로 만들 경우
    int BpaintCount = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (map[i + x][j + y] != Bchess[i][j]) {
                BpaintCount++;
            }
        }
    }
 
    //왼쪽 위가 W인 체스판으로 만들 경우
    int WpaintCount = 0;
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (map[i + x][j + y] != Wchess[i][j]) {
                WpaintCount++;
            }
        }
    }
 
    //최소값 반환
    return min(BpaintCount, WpaintCount);
}
 
int main() {
 
    //초기화
    answer = -1;
 
    //입력
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string tmp;
        cin >> tmp;
        map.push_back(tmp);
    }
 
    //해법
    for (int i = 0; i <= N - 8; i++) {
        for (int j = 0; j <= M - 8; j++) {
 
            int minPaint = minPaintCount(i, j);
            
            //결과 갱신
            if (answer == -1 || minPaint < answer) {
                answer = minPaint;
            }
        }
    }
 
    //출력
    cout << answer;
 
    //종료
    return 0;
}
 

 

구현과 브루트포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 2447 - 별 찍기 10  (0) 2021.01.14
[C++] 백준 12100 - 2048(Easy)  (0) 2021.01.10
[C++] 백준 14502 - 연구소  (0) 2021.01.03
[C++] 백준 1120 - 문자열  (0) 2021.01.03
[C++] 백준 4949 - 균형잡힌 세상  (0) 2021.01.01

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi&categoryId=AV14QpAaAAwCFAYi&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

<풀이>

1. 8x8 글자판을 입력받는다.

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
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 <string>
#include <string.h>
 
using namespace std;
 
int palindrome_length;
char map[8][8];
int answer;
 
//해당 문자열이 회문인지 판단하는 함수
bool isPalindrome(string s) {
 
    for (int i = 0; i < s.length() / 2; i++) {
        if (s[i] != s[s.length() - 1 - i]) {
            return false;
        }
    }
 
    return true;
}
 
//해당 좌표에 회문이 몇 개인지 판단하는 함수
int countPalindrome(int x, int y) {
 
    int palindromeCnt = 0;
 
    //아래쪽에 회문이 있는지 확인
    if (x + palindrome_length <= 8) {
 
        //아래쪽 문자열을 모으고
        string str = "";
        for (int i = 0; i < palindrome_length; i++) {
            str += map[x + i][y];
        }
 
        //문자열이 회문인지 확인
        if (isPalindrome(str)) {
            palindromeCnt++;
        }
    }
 
    //오른쪽에 회문이 있는지 확인
    if (y + palindrome_length <= 8) {
 
        //오른쪽 문자열을 모으고
        string str = "";
        for (int i = 0; i < palindrome_length; i++) {
            str += map[x][y + i];
        }
 
        //문자열이 회문인지 확인
        if (isPalindrome(str)) {
            palindromeCnt++;
        }
    }
 
    return palindromeCnt;
}
 
int main() {
 
    int test_case;
    int T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        palindrome_length = 0;
        memset(map, '#', sizeof(map));
        answer = 0;
 
        //입력
        cin >> palindrome_length;
        for (int i = 0; i < 8; i++) {
            string tmp;
            cin >> tmp;
            for (int j = 0; j < 8; j++) {
                map[i][j] = tmp[j];
            }
        }
 
        //해법
        /*
        각 좌표마다 아래쪽 또는 오른쪽 방향에 회문이 있는지 확인
        */
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                answer += countPalindrome(i, j);
            }
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 2805 - 농작물 수확하기  (0) 2021.01.08
[C++] SWEA 2817 - 부분 수열의 합  (0) 2021.01.08
[C++] SWEA 1208 - Flattern  (0) 2021.01.02
[C++] SWEA 1244 - 최대 상금  (0) 2020.12.31
[C++] SWEA 2112 - 보호 필름  (0) 2020.05.19

programmers.co.kr/learn/courses/30/lessons/17678

 

코딩테스트 연습 - [1차] 셔틀버스

10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00

programmers.co.kr

<풀이>

1. 셔틀버스 정보와 크루들의 정보를 입력받는다.

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
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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
priority_queue<int, vector<int>, greater<int>> timetable_int;
queue<int> line;
 
//문자열 시간 -> int 시간으로 바꾸기
int toIntTime(string time) {
 
    int res = 0;
 
    int hour = stoi(time.substr(0, 2)) * 60;
    int minute = stoi(time.substr(3, 2));
 
    res = hour + minute;
 
    return res;
}
 
//int 시간 -> 문자열 시간으로 바꾸기
string toStringTime(int time) {
 
    string res = "";
 
    string hour = to_string(time / 60);
    if (hour.length() < 2) {
        hour = "0" + hour;
    }
 
    string minute = to_string(time % 60);
    if (minute.length() < 2) {
        minute = "0" + minute;
    }
 
    res = hour + ":" + minute;
 
    return res;
}
 
string solution(int n, int t, int m, vector<string> timetable) {
 
    string answer = "";
 
    //정답으로 바꿀 int형 시간
    int answerTime_int = 0;
 
    //문자열 시간을 int형 시간으로 바꾼 후, 우선순위 큐에 저장
    for (int i = 0; i < timetable.size(); i++) {
 
        int time = toIntTime(timetable[i]);
 
        timetable_int.push(time);
    }
    
    //셔틀 버스 반복 수행
    for (int i = 0; i < n; i++) {
 
        //버스 오는 시간
        int busTime = 540 + i * t;
 
        //버스 오는 시간 전까지 도착한 사람 줄 세우기
        while (true) {
            if (timetable_int.empty() || timetable_int.top() > busTime) {
                break;
            }
            line.push(timetable_int.top());
            timetable_int.pop();
        }
 
        /*
        줄 서 있는 사람 수 < 버스에 태울 수 있는 사람 수 일 경우,
        버스가 오는 시간에 맞춰 도착하면 된다.
        */
        if (line.size() < m) {
            answerTime_int = busTime;
            for (int j = 0; j < line.size(); j++) {
                line.pop();
            }
        }
        /*
        줄 서 있는 사람 >= 버스에 태울 수 있는 사람 수 일 경우,
        버스에 탈 수 있는 마지막 사람보다 1분 일찍오면 된다.
        */
        else {
            for (int j = 0; j < m - 1; j++) {
                line.pop();
            }
            answerTime_int = line.front() - 1;
            line.pop();
        }
    }
 
    //결과
    answer = toStringTime(answerTime_int);
 
    //결과 반환
    return answer;
}
 

 

시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 캐시  (0) 2021.01.11
[C++] 프로그래머스 - 프렌즈4블록  (0) 2021.01.07
[C++] 프로그래머스 - 뉴스 클러스터링  (0) 2021.01.01
[C++] 프로그래머스 - 추석 트래픽  (0) 2020.12.29
[C++] 프로그래머스 - 후보키  (0) 2020.05.15

+ Recent posts

티스토리툴바