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

 

코딩테스트 연습 - [1차] 추석 트래픽

입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748

programmers.co.kr

<풀이>

1. 주어진 문자열을 통해 '요청 시작 시간'과 '처리 완료 시간'을 분리합니다.

2. 초당 최대 처리량을 결과값으로 저장합니다.

3. 결과를 반환합니다.

 

<해법>

1. 문자열 문제 마음가짐

=> 문자열 문제를 마주했을 때, 가장 먼저 '문자열을 다루는 함수'를 적극적으로 사용하겠다는 마음가짐을 가져야합니다. 저는 문자열 문제를 풀 때, 간단한 조건식으로 풀 수 있는 문제라도 문자열을 다루는 함수를 적극적으로 사용하여 문제를 풉니다.

 

2. 시간 계산

=> 초당 최대 처리량을 구하기 위해서는 각 문자열 마다 '요청 시작 시간'을 알아야합니다. 또, '요청 시작 시간'을 구하기 위해서는 시간을 계산할 수 있는 형태로 만들어야 합니다. 그래서, 저는 시간을 millisecond형태로 바꾸어서 계산하였습니다.

 

3. 초당 최대 처리량을 구하는 방법

=> 시간은 '응답 완료 시간'을 기준으로 오름차순 되어있습니다. 각 시간의 '응답 완료 시간'부터 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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
//구조 : 시간(시작 시간, 끝 시간)
struct Time {
    int start_time, end_time;
};
 
int solution(vector<string> lines) {
 
    int answer = 0;
 
    vector<Time> v;
 
    //문자열 파싱
    for (int i = 0; i < lines.size(); i++) {
        string h, m, s, process;
        int int_h, int_m, int_s, int_process;
 
        //시, 분, 초, 처리시간 파싱 (ex. "2016-09-15 20:59:57.421 0.351s")
        h = lines[i].substr(11, 2); //"20"
        m = lines[i].substr(14, 2); //"59"
        s = lines[i].substr(17, 6); //"57.421"
        process = lines[i].substr(24); //"0.351s"
        process = process.substr(0, process.length() - 1); //"0.351"
 
        //string -> int
        int_h = stoi(h) * 60 * 60 * 1000;
        int_m = stoi(m) * 60 * 1000;
        int_s = stod(s) * 1000;
        int_process = stod(process) * 1000;
 
        //시간 변수(시작시간, 끝시간) 생성 
        int end_time = int_h + int_m + int_s;
        int start_time = end_time - int_process + 1;
        Time t = { start_time, end_time };
 
        //저장
        v.push_back(t);
    }
 
    //초당 최대 처리량 구하기
    for (int i = 0; i < v.size(); i++) {
 
        int tmpAnswer = 0;
 
        Time t = v[i];
        int check_time = t.end_time + 1000 - 1;
 
        //끝 시간 보다 시작 시간이 작다면, 처리량 + 1
        for (int j = i; j < v.size(); j++) {
            if (v[j].start_time <= check_time) {
                tmpAnswer++;
            }
        }
 
        //최대 처리량 갱신
        if (tmpAnswer > answer) {
            answer = tmpAnswer;
        }
    }
 
    return answer;
}
 

 

문자열 처리에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 프로그래머스 - 셔틀버스  (0) 2021.01.04
[C++] 프로그래머스 - 뉴스 클러스터링  (0) 2021.01.01
[C++] 프로그래머스 - 후보키  (0) 2020.05.15
[C++] 프로그래머스 - 실패율  (0) 2020.05.15
[C++] 프로그래머스 - 불량 사용자  (0) 2020.05.15

www.acmicpc.net/problem/2636

 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

<풀이>

1. 치즈 맵을 입력받는다.

2. 바깥쪽 공기와 맞닿는 치즈를 없앤다.

3. 치즈가 모두 없어졌을 때까지 걸린 시간과, 그 전 치즈 개수를 출력한다.

 

<해법>

1. 바깥쪽 공기와 맞닿는 치즈를 없애는 방법

=> 탐색(BFS, DFS) 이용합니다. 탐색을 이용해서 바깥쪽 공기가 어디까지 퍼져있는지 확인합니다. 탐색 진행 도중에 치즈를 발견했을 경우, 바깥 공기와 맞닿는 치즈이므로 치즈를 없애는 식으로 진행하였습니다.

 

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
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
//4방향 : 북,동,남,서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int height, width;
int map[100][100];
bool visited[100][100];
 
int resTime = 0;
int resCheeze = 0;
 
//구조 : 좌표
struct pos {
    int x, y;
};
 
//맵에 치즈가 없는지 확인 : 없으면 true, 있으면 false
bool noCheeze() {
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1) {
                return false;
            }
        }
    }
    return true;
}
 
//치즈 없애기
void removeCheeze() {
    
    //방문 배열 초기화
    memset(visited, false, sizeof(visited));
 
    //바깥쪽 공기만 탐색
    queue<pos> q;
    q.push({ 0,0 });
    visited[0][0] = true;
 
    while (!q.empty()) {
        pos cur = q.front();
        q.pop();
 
        //4방향 탐색
        for (int i = 0; i < 4; i++) {
            pos nxt = cur;
            nxt.x += di[i];
            nxt.y += dj[i];
 
            //범위 밖 or 방문했던 경우 -> continue
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= height || nxt.y >= width || visited[nxt.x][nxt.y]) {
                continue;
            }
 
            //공기일 경우 -> 큐에 넣기(계속 탐색을 해야하므로)
            if (map[nxt.x][nxt.y] == 0) {
                q.push(nxt);
            }
            //치즈일 경우 -> 바깥 공기와 맞닿는 치즈이므로 공기로 바꾸어줌, 큐에 담지 않음(더 이상 탐색X)
            else {
                map[nxt.x][nxt.y] = 0;
            }
            visited[nxt.x][nxt.y] = true;
        }
    }
 
}
 
//치즈 개수 세기
int countCheeze() {
    int output = 0;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1) {
                output++;
            }
        }
    }
    return output;
}
 
int main() {
 
    //입력
    cin >> height >> width;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            cin >> map[i][j];
        }
    }
 
    while (true) {
 
        //치즈가 없을 경우 -> 종료
        if (noCheeze()) {
            break;
        }
 
        //치즈 개수 갱신
        resCheeze = countCheeze();
 
        //치즈 없애기
        removeCheeze();
 
        //시간 + 1
        resTime++;
    }
 
    //출력
    cout << resTime << "\n" << resCheeze;
}
 

 

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

저작자표시

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

[C++] 백준 10773 - 제로  (0) 2021.01.01
[C++] 백준 1764 - 듣보잡  (0) 2021.01.01
[C++] 백준 2941 - 크로아티아 알파벳  (0) 2020.12.27
[Python] 백준 10834 - 벨트  (0) 2020.06.21
[Python] 백준 10833 - 사과  (0) 2020.06.21

www.acmicpc.net/problem/2941

 

2941번: 크로아티아 알파벳

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z=

www.acmicpc.net

<풀이>

1. 문자열을 입력받습니다.

2. 입력된 문자열에 크로아티아 문자열이 있는지 찾고, 한 문자로 변경합니다.

3. 바뀐 문자열의 길이를 출력합니다.

 

<해법>

1. 문자열 문제 마음가짐

=> 문자열 문제를 마주했을 때, 가장 먼저 '문자열 다루는 함수'를 적극적으로 사용하겠다는 생각을 해야합니다. 위 문제도 사실 굳이 문자열 다루는 함수를 사용하지 않더라도 많은 조건문으로 풀 수 있습니다. 직관적으로 풀 수 있다는 장점이 있지만, 코드가 길어져서 지저분해질 뿐만 아니라 많은 예외 처리를 해야 합니다. 하지만, '문자열 다루는 함수를 사용해야겠다.' 라는 마음가짐만 갖고 시작하더라도 문제를 좀 더 쉽게 풀 수 있습니다.

 

2. 입력된 문자열에서 크로아티아 문자열을 찾는 방법, 크로아티아 문자열 바꾸기

=> string의 find함수, string의 replace함수 사용하기

 

아래 잘 정리된 블로그를 참고하시면 좋을 것 같습니다.

blockdmask.tistory.com/338

 

[C++] string 클래스, 문자열에 대해서 (총정리)

안녕하세요 BlockDMask 입니다. 오늘은 C++의 std::string 클래스(문자열)에 대해서 세세 하게 알아볼것 입니다. 예전 글을 보다가 제가 작성한 이 문서를 보게 되었는데요, 너무 내용이 빈약하다고

blockdmask.tistory.com

 

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 <string>
#include <vector>
 
using namespace std;
 
//c=, c-, dz=, d-, lj, nj, s=, z=
vector<string> croatia = { "c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z=" };
 
string input;
 
//결과
int res = 0;
 
int main() {
 
    //입력 ex) input : ddz=z=
    cin >> input;
 
    for (int i = 0; i < croatia.size(); i++) {
        //크로아티아 문자열 찾기
        while (true) {
            int index = input.find(croatia[i]);
 
            //크로아티아 문자열이 없을 경우
            if (index == string::npos) {
                break;
            }
 
            //크로아티아 문자열 -> "#"으로 바꾸기
            input.replace(index, croatia[i].length(), "*");
        }
    }
 
    //ex) input : d**
    res = input.length();
 
    //출력
    cout << res << "\n";
}

 

문자열 다루는 방법에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 1764 - 듣보잡  (0) 2021.01.01
[C++] 백준 2636 - 치즈  (0) 2020.12.28
[Python] 백준 10834 - 벨트  (0) 2020.06.21
[Python] 백준 10833 - 사과  (0) 2020.06.21
[C++] 백준 8981 - 입력숫자  (0) 2020.04.30

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

 

10834번: 벨트

첫 줄에는 벨트의 개수를 나타내는 자연수 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 M개의 줄에는 1번 벨트부터 순서대로 벨트로 이어진 두 바퀴의 회전수의 비를 나타내는 두 개의 양의 정수 a, b와 벨��

www.acmicpc.net

<풀이>

1. 벨트 개수를 입력받는다.

2. 각 벨트마다 다음 바퀴의 방향과 회전 수를 저장한다.

3. 결과를 출력한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def main() :
 
    # 입력
    M = int(input())
 
    # 초기화
    resultDir = 0
    resultCnt = 1
    
    # 구현
    for _ in range(M) :
        first, second, dir = map(int, input().split())
        resultDir = resultDir ^ dir
        resultCnt = resultCnt // first * second
 
    # 출력
    print(resultDir, resultCnt)
 
if __name__ == '__main__' :
    main()
 

 

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

저작자표시

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

[C++] 백준 2636 - 치즈  (0) 2020.12.28
[C++] 백준 2941 - 크로아티아 알파벳  (0) 2020.12.27
[Python] 백준 10833 - 사과  (0) 2020.06.21
[C++] 백준 8981 - 입력숫자  (0) 2020.04.30
[C++] 백준 8980 - 택배  (0) 2020.04.30

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

 

10833번: 사과

경상북도 특산품인 사과를 학생들에게 나눠주기 위해 여러 학교에 사과를 배정하였다. 배정된 사과 개수는 학교마다 다를 수 있고, 학생 수도 학교마다 다를 수 있다. 각 학교에서는 배정된 사��

www.acmicpc.net

<풀이>

1. 학교 수를 입력받는다.

2. 각 학교마다 입력받는 사과 수를 학생 수로 나눈 나머지의 합을 구한다.

3. 결과를 출력한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def main() :
 
    # 입력
    N = int(input())
 
    # 초기화
    result = 0
 
    # 구현
    for i in range(0,N,1) :
        student, apple = map(int, input().split())
        result += (apple % student)
 
    # 출력
    print(result)
 
if __name__ == '__main__' :
    main()
 

 

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

저작자표시

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

[C++] 백준 2941 - 크로아티아 알파벳  (0) 2020.12.27
[Python] 백준 10834 - 벨트  (0) 2020.06.21
[C++] 백준 8981 - 입력숫자  (0) 2020.04.30
[C++] 백준 8980 - 택배  (0) 2020.04.30
[C++] 백준 2512 - 예산  (0) 2020.04.30

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 각 열마다 어떤 약품을 투입할 것인지 결정한다.

2. 결정된 약품을 각 열에 투입하고, 성능검사를 한다.

3. 성능검사에 통과된 약품 투입횟수 중 최솟값을 출력한다.

 

<해법>

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
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
#include <iostream>
#include <cstring>
using namespace std;
 
int D, W, K;
int map[13][20];
int tmpMap[13][20];
int medicine[13];
int res;
 
void go(int index, int medicineCnt) {
 
    //사용한 약품 개수는 합격 기준보다 많을 경우 -> 탐색 필요X
    if (medicineCnt > K) {
        return;
    }
 
    //결과값보다 많은 약품을 사용할 경우 -> 탐색 필요X
    if (res >= 0 && medicineCnt > res) {
        return;
    }
 
    //약품 선택 완료 -> 종료조건
    if (index == D) {
        
        memcpy(tmpMap, map, sizeof(tmpMap));
 
        //약품 투입
        for (int i = 0; i < D; i++) {
            if (medicine[i] == -1) {
                continue;
            }
            for (int j = 0; j < W; j++) {
                tmpMap[i][j] = medicine[i];
            }
        }
 
        //보호필름 검사
        bool isAble = true;
        //각 열마다 행 탐색
        for (int i = 0; i < W; i++) {
            int cnt = 1;
            for (int j = 0; j < D - 1; j++) {
                
                //다음 행과 비교
                if (tmpMap[j][i] == tmpMap[j + 1][i]) {
                    cnt++;
                }
                else {
                    cnt = 1;
                }
 
                if (cnt == K) {
                    break;
                }
            }
 
            if (cnt < K) {
                isAble = false;
                break;
            }
        }
 
        //결과 저장
        if (isAble) {
            if (res == -1 || medicineCnt < res) {
                res = medicineCnt;
            }
        }
 
        //종료
        return;
    }
 
    //medicine[index] -> index열에 어떤 약품이 칠해지는지 저장
    //-1 : 약품X, 0 : A약품, 1 : B약품
    for (int i = -1; i <= 1; i++) {
        medicine[index] = i;
        if (i == -1) {
            go(index + 1, medicineCnt);
        }
        else {
            //약품을 칠한 경우, 사용한 약품 개수 + 1
            go(index + 1, medicineCnt + 1);
        }
    }
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        memset(medicine, 0, sizeof(medicine));
        res = -1;
 
        //입력
        cin >> D >> W >> K;
        for (int i = 0; i < D; i++) {
            for (int j = 0; j < W; j++) {
                cin >> map[i][j];
            }
        }
 
        //약품 칠하고 보호필름 검사(재귀함수)
        go(0, 0);
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
 
    return 0;
}
 

 

백트래킹에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 1208 - Flattern  (0) 2021.01.02
[C++] SWEA 1244 - 최대 상금  (0) 2020.12.31
[C++] SWEA 2117 - 홈 방범 서비스  (0) 2020.05.19
[C++] SWEA 5656 - 벽돌 깨기  (0) 2020.05.19
[C++] SWEA 5650 - 핀볼 게임  (0) 2020.05.15

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 모든 도시 좌표에서 서비스 제공을 시작한다.

2. 각 좌표에서 시작해서 서비스 영역을 넓혀가며, 그 때 마다 이윤을 구하고 최댓값을 저장한다.

3. 결과를 출력한다.

 

<해법>

1. 각 좌표에서 서비스 영역을 넓혀가는 방법.

=> 각 좌표에서 넓혀지는 서비스 영역이, 2차원 배열에서 BFS를 이용해 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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct pos {
    //좌표
    int x, y;
};
 
//4방향
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, M;
int map[20][20];
bool visited[20][20];
int res;
 
//범위 내에 있는지 판단
bool inner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) {
        return false;
    }
    return true;
}
 
int bfs(pos str) {
 
    //초기화
    memset(visited, false, sizeof(visited));
 
    queue<pos> q;
    q.push(str);
    visited[str.x][str.y] = true;
 
    int K = 0, cnt = 0, MAX = 0;
 
    while (!q.empty()) {
        int qsize = q.size();
        K++;
        
        //서비스 영역부분 탐색
        for (int i = 0; i < qsize; i++) {
            pos cur = q.front();
            q.pop();
 
            //집 개수 세기
            if (map[cur.x][cur.y] == 1) {
                cnt++;
            }
 
            //4방향 탐색
            for (int j = 0; j < 4; j++) {
                pos nxt = cur;
                nxt.x += di[j];
                nxt.y += dj[j];
 
                if (!inner(nxt.x, nxt.y)) {
                    continue;
                }
                if (visited[nxt.x][nxt.y]) {
                    continue;
                }
                
                q.push(nxt);
                visited[nxt.x][nxt.y] = true;
            }
        }
 
        //이윤 계산
        int profit = (cnt * M) - ((K * K) + (K - 1) * (K - 1));
        
        //손해보지 않는 경우, 집 개수 계산
        if (profit >= 0) {
            if (cnt > MAX) {
                MAX = cnt;
            }
        }
    }
 
    return MAX;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        res = 0;
 
        //입력
        cin >> N >> M;    
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        //모든 좌표마다 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                pos str = { i,j };
                int tmp = bfs(str);
 
                if (tmp > res) {
                    res = tmp;
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
 
    return 0;
}
 

 

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

저작자표시

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

[C++] SWEA 1244 - 최대 상금  (0) 2020.12.31
[C++] SWEA 2112 - 보호 필름  (0) 2020.05.19
[C++] SWEA 5656 - 벽돌 깨기  (0) 2020.05.19
[C++] SWEA 5650 - 핀볼 게임  (0) 2020.05.15
[C++] SWEA 5644 - 무선 충전  (0) 2020.05.15

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

 

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
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
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct brick {
    //위치
    int x, y;
    //
    int cnt;
};
 
//4방향
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, W, H;
int map[15][12];
int tmpMap[15][12];
int ball[4];
int res;
 
void down() {
 
    //빈칸 위에 벽돌이 있을 경우, 벽돌 내리기
    for (int i = 0; i < W; i++) {
        //가장 아래칸부터 탐색
        for (int j = H - 1; j >= 0; j--) {
            if (tmpMap[j][i] == 0) {
                //빈칸 위에 벽돌이 있는 경우 -> 빈칸과 벽돌 위치 바꾸기
                for (int k = j - 1; k >= 0; k--) {
                    if (tmpMap[k][i] > 0) {
                        tmpMap[j][i] = tmpMap[k][i];
                        tmpMap[k][i] = 0;
                        break;
                    }
                }
            }
        }
    }
}
 
void go(int index) {
     
    //종료 조건 : 떨어트릴 구슬 위치 선택 완료
    if (index == N) {
 
        //초기화
        memcpy(tmpMap, map, sizeof(tmpMap));
        int cnt = 0;
 
        //N개 구슬 떨어트리기
        for (int i = 0; i < N; i++) {
 
            queue<brick> q;
 
            //구슬 떨어트리고, 가장 처음 터지는 벽돌 큐에 담기
            for (int j = 0; j < H; j++) {
                if (tmpMap[j][ball[i]] > 0) {
                    q.push({ j,ball[i],tmpMap[j][ball[i]] });
                    tmpMap[j][ball[i]] = 0;
                    break;
                }
            }
 
            //벽돌이 모두 터질때 까지 터트리기
            while (!q.empty()) {
 
                brick cur = q.front();
                q.pop();
 
                //4방향 모두 터트리기
                for (int j = 0; j < 4; j++) {
                    brick nxt = cur;
                    //(벽돌 길이 - 1) 만큼 터트리기
                    for (int k = 0; k < cur.cnt - 1; k++) {
 
                        nxt.x += di[j];
                        nxt.y += dj[j];
 
                        //범위를 넘어섰을 경우
                        if (nxt.x < 0 || nxt.y < 0 || nxt.x >= H || nxt.y >= W) {
                            break;
                        }
                        //벽돌이 아닐경우
                        if (tmpMap[nxt.x][nxt.y] == 0) {
                            continue;
                        }
 
                        //터지는 벽돌 큐에 담기
                        nxt.cnt = tmpMap[nxt.x][nxt.y];
                        q.push(nxt);
                        tmpMap[nxt.x][nxt.y] = 0;
                    }
                }
            }
 
            //벽돌 떨어트리기
            down();
        }
 
        //결과 계산 및 저장
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (tmpMap[i][j] > 0) {
                    cnt++;
                }
            }
        }
        if (res == -1 || cnt < res) {
            res = cnt;
        }
        return;
    }
 
    //떨어트릴 구슬 위치 저장(재귀함수)
    for (int i = 0; i < W; i++) {
        ball[index] = i;
        go(index + 1);
    }
 
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        memset(tmpMap, 0, sizeof(tmpMap));
        memset(ball, 0, sizeof(ball));
        res = -1;
 
        //입력
        cin >> N >> W >> H;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> map[i][j];
            }
        }
 
        //떨어트릴 구슬 위치 구하고, 결과값 저장
        go(0);
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
 
    return 0;
}
 

 

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

저작자표시

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

[C++] SWEA 2112 - 보호 필름  (0) 2020.05.19
[C++] SWEA 2117 - 홈 방범 서비스  (0) 2020.05.19
[C++] SWEA 5650 - 핀볼 게임  (0) 2020.05.15
[C++] SWEA 5644 - 무선 충전  (0) 2020.05.15
[C++] SWEA 2383 - 점심 식사시간  (0) 2020.05.03

+ Recent posts

티스토리툴바