https://school.programmers.co.kr/learn/courses/30/lessons/150369

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 배달해야할 박스 갯수와 수거해야할 박스 갯수 정보를 입력받는다.

2. 모든 배달과 수거를 마치고 물류창고로 돌아오는 최소거리를 반환한다.

 

<해법>

1. 알고리즘 선택하기

=> 가장 끝에서 부터 가능한 배달과 수거를 최대로 하면 정답을 구할 수 있습니다. 따라서, 저는 그리디 알고리즘을 선택했습니다.

 

2. 자료구조 선택하기

=> 가장 끝에서 부터 배달과 수거를 진행합니다. 그리고 배달과 수거가 완료된 집은 넘어갑니다. 따라서, 저는 후입선출 자료구조인 스택을 선택했습니다.

 

3. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 끝 집에서 부터 배달과 수거를 진행한다. 이동한 거리는 max(배달해야할 끝집, 수거해야할 끝집) x 2 이다.

(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
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
struct house {
    int idx, boxCnt;
};
 
stack<house> del, pic;
 
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
 
    for (int i = 0; i < deliveries.size(); i++) {
        int boxCnt = deliveries[i];
        if (boxCnt) {
            del.push({ i + 1, boxCnt });
        }
    }
    for (int i = 0; i < pickups.size(); i++) {
        int boxCnt = pickups[i];
        if (boxCnt) {
            pic.push({ i + 1, boxCnt });
        }
    }
 
    while (true) {
        if (del.empty() && pic.empty()) break;
 
        int delIdx = del.empty() ? 0 : del.top().idx;
        int picIdx = pic.empty() ? 0 : pic.top().idx;
        answer += static_cast<long long>(max(delIdx, picIdx)) * 2;
 
        int delBoxCnt = 0;
        while (!del.empty()) {
            house& h = del.top();
            if (delBoxCnt + h.boxCnt <= cap) {
                delBoxCnt += h.boxCnt;
                del.pop();
            }
            else {
                h.boxCnt -= (cap - delBoxCnt);
                break;
            }
        }
 
        int picBoxCnt = 0;
        while (!pic.empty()) {
            house& h = pic.top();
            if (picBoxCnt + h.boxCnt <= cap) {
                picBoxCnt += h.boxCnt;
                pic.pop();
            }
            else {
                h.boxCnt -= (cap - picBoxCnt);
                break;
            }
        }
    }
 
    return answer;
}

 

그리디 알고리즘에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 프로그래머스 - 표현 가능한 이진트리  (0) 2023.02.02
[C++] 프로그래머스 - 이모티콘 할인행사  (0) 2023.02.01
[C++] 프로그래머스 - 개인정보 수집 유효기간  (0) 2023.02.01
[C++] 프로그래머스 - 코딩 테스트 공부  (0) 2022.08.24
[C++] 프로그래머스 - 두 큐 합 같게 만들기  (0) 2022.08.24

https://school.programmers.co.kr/learn/courses/30/lessons/150370

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 현재 날짜, 약관 정보, 개인 정보를 입력받는다.

2. 유효기간이 지난 개인 정보의 번호를 반환한다.

 

<해법>

1. 날짜 문자열 연산 및 대소비교 방법

=> 위 문제는 "개인정보 수집 날짜 + 유효기간  < 오늘 날짜" 를 물어보는 것입니다. 이제 핵심은 날짜 연산 및 대소비교 입니다. 날짜 문자열을 가장 쉽게 연산과 대소비교를 하는 방법은 모두 정수로 바꿔서 계산하는 것입니다. 위 문제의 경우 모두 일 수로 바꾸면 연산과 대소비교를 빠르게 할 수 있습니다. 코드의 dateStringToInt 함수를 참고해주세요. 날짜나 시간 등등 문자열을 쉽고 빠르게 연산하고 대소비교하는 방법은 정수로 바꾸는 것입니다.

 

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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
 
using namespace std;
 
map<char, int> m;
 
int dateStringToInt(string str) {
    int year = stoi(str.substr(0, 4));
    int month = stoi(str.substr(5, 2));
    int day = stoi(str.substr(8));
    return (28 * 12 * year) + (28 * (month - 1)) + day;
}
 
int calcDate(int d, int num) {
    return d + (28 * num) - 1;
}
 
vector<int> solution(string today, vector<string> terms, vector<string> privacies) {
    vector<int> answer;
 
    int td = dateStringToInt(today);
 
    for (string& t : terms) {
        istringstream iss(t);
        char cmd;
        int num;
        iss >> cmd >> num;
        m[cmd] = num;
    }
 
    for (int i = 0; i < privacies.size(); i++) {
        istringstream iss(privacies[i]);
        string s;
        char cmd;
        iss >> s >> cmd;
 
        int d = dateStringToInt(s);
        int expired = calcDate(d, m[cmd]);
        if (expired < td) answer.push_back(i + 1);
    }
 
    return answer;
}

 

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

저작자표시

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

[C++] 프로그래머스 - 이모티콘 할인행사  (0) 2023.02.01
[C++] 프로그래머스 - 택배 배달과 수거하기  (0) 2023.02.01
[C++] 프로그래머스 - 코딩 테스트 공부  (0) 2022.08.24
[C++] 프로그래머스 - 두 큐 합 같게 만들기  (0) 2022.08.24
[C++] 프로그래머스 - 성격 유형 검사하기  (0) 2022.08.24

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 벽돌 보드를 입력받는다.

2. N개의 구슬을 쏘아서 가장 많은 벽돌이 제거되는 경우를 찾고, 그 때 남은 벽돌의 개수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 구슬을 쏘는 모든 경우를 다 해보아야 합니다. 따라서, 저는 브루트포스를 선택했습니다. 

 

2. 벽돌 깨트리기

=> 저는 DFS를 선택했습니다. 4방향을 벽돌의 power만큼 탐색하면서 벽돌을 깨트렸습니다. 사실 구현은 DFS, BFS 큰 상관이 없다고 생각합니다.

 

3. 벽돌 내리기

=> 벽돌을 깨트렸으면, 이제 벽돌을 빈공간으로 내려야합니다. 저는 큐(Queue)를 선택했습니다. 아래서 부터 벽돌인 것만 큐에 차례로 담고, 나중에 다시 벽돌을 쌓는 개념으로 구현하였습니다. 자세한 구현은 코드의 fallBrick() 함수를 참조해주세요.

 

4. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 구슬을 쏘는 위치는 재귀함수로 구현한다. 최악의 경우 12P4 이므로, 시간초과하지 않는다.

(2) 구슬의 위치를 다 결정하고 시뮬레이션을 할까, 구슬의 위치를 정할 때마다 시뮬레이션을 할까?

: 구슬의 위치를 정할 때마다 시뮬레이션을 진행한다. 구슬의 위치 [1,2,3,4]와 [1,2,3,5]는 구슬을 [1,2,3] 떨어트렸을 때까지 상황이 동일하다. 따라서, 시간을 줄이기 위해 구슬의 위치 정하고 바로 구슬을 떨어트려본다.

(3) 벽돌 깨트리는 것은 재귀함수로 구현한다.

(4) 벽돌 내릴 때는 큐를 이용해 구현한다.

(5) 남은 벽돌 개수의 최소를 구하는 것이므로, 반대로 얘기하면 깨트린 벽돌 개수의 최대를 구하는 것과 같다. 따라서, (처음 벽돌 개수) - (깨트린 벽돌 개수 max)를 출력한다.

자세한 구현은 아래 코드를 참조해주세요.

 

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.h>
#include <algorithm>
#include <queue>
#define INF 987654321
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, W, H;
int map[15][12];
int totalBricks;
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= H || y >= W) return false;
    return true;
}
 
int removeBrick(int x, int y) {
    int power = map[x][y];
    map[x][y] = 0;
    int ret = 1;
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j < power; j++) {
            int nx = x + (dx[i] * j);
            int ny = y + (dy[i] * j);
            if (!isInner(nx, ny)) break;
            if (map[nx][ny] > 0) {
                ret += removeBrick(nx, ny);
            }
        }
    }
    return ret;
}
 
void fallBrick() {
    for (int j = 0; j < W; j++) {
        queue<int> q;
        for (int i = H - 1; i >= 0; i--) {
            if (map[i][j] > 0) q.push(map[i][j]);
            map[i][j] = 0;
        }
        int col = H - 1;
        while (!q.empty()) {
            map[col][j] = q.front();
            q.pop();
            col--;
        }
    }
}
 
int simulation(int col) {
    int removedBricks = 0;
    for (int i = 0; i < H; i++) {
        if (map[i][col] > 0) {
            removedBricks = removeBrick(i, col);
            fallBrick();
            break;
        }
    }
    return removedBricks;
}
 
int selectBallPos(int cnt) {
    if (cnt == N) return 0;
 
    int ret = 0;
    int backup[15][12];
    memcpy(backup, map, sizeof(backup));
    for (int i = 0; i < W; i++) {
        int removedBricks = simulation(i);
        ret = max(ret, selectBallPos(cnt + 1) + removedBricks);
        memcpy(map, backup, sizeof(map));
    }
    return ret;
}
 
void solution() {
    answer = totalBricks - selectBallPos(0);
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0, W = 0, H = 0;
        memset(map, 0, sizeof(map));
        totalBricks = 0;
        answer = 0;
 
        //입력
        cin >> N >> W >> H;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> map[i][j];
                if (map[i][j] > 0) totalBricks++;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

브루트포스, DFS, 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 1232 - 사칙연산  (1) 2022.12.31
[C++] SWEA 1233 - 사칙연산 유효성 검사  (0) 2022.12.31
[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD&categoryId=AV141J8KAIcCFAYD&categoryType=CODE&problemTitle=1232&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 트리를 입력받는다

2. 트리를 연산한 결과를 출력한다.

 

<해법>

1. 트리를 구현하는 방법

=> 저는 노드 구조체를 만들어서 구현하였습니다. 구조체에는 data와 왼쪽 자식, 오른쪽자식의 index가 있습니다.

 

2. 트리를 연산하는 방법

=> 저는 트리를 후위순회 하였습니다. 또한, 숫자는 leaf노드에만 존재하므로 노드의 데이터가 연산자면 자식노드들을 탐색하고, 숫자노드면 바로 숫자 데이터를 return하는 것으로 구현하였습니다.

 

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
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
struct node {
    string data;
    int leftNode, rightNode;
};
 
int N;
node arr[1001];
int answer;
 
bool isOper(string s) {
    if (s == "+" || s == "-" || s == "*" || s == "/") return true;
    return false;
}
 
double calculate(double a, string oper, double b) {
    double output = 0;
    if (oper == "+") output = a + b;
    else if (oper == "-") output = a - b;
    else if (oper == "*") output = a * b;
    else output = a / b;
    return output;
}
 
double postOrder(int idx) {
    if (!isOper(arr[idx].data)) return stoi(arr[idx].data);
 
    double ret = 0;
    ret = calculate(postOrder(arr[idx].leftNode), arr[idx].data, postOrder(arr[idx].rightNode));
    return ret;
}
 
void solution() {
    answer = postOrder(1);
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        for (int i = 0; i < 1001; i++) arr[i] = { "",0,0 };
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            string data;
            cin >> idx >> data;
            arr[idx].data = data;
            if (isOper(data)) {
                int leftNode, rightNode;
                cin >> leftNode >> rightNode;
                arr[idx].leftNode = leftNode, arr[idx].rightNode = rightNode;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

자료구조 트리와 재귀함수에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 5656 - 벽돌 깨기(2)  (0) 2023.01.02
[C++] SWEA 1233 - 사칙연산 유효성 검사  (0) 2022.12.31
[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=1233&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 트리 정보를 입력받는다.

2. 해당 트리 연산식의 유효성을 출력한다.

 

<해법>
1. 트리 연산식의 유효성을 판단하는 방법

=> 계산되는 방법을 살펴보면, 연산자 노드는 자식이 있어야하고 숫자 노드는 자식이 없어야합니다. 또한 연산자 노드는 자식이 꼭 2개여야 합니다. 저는 입력받을 때, 연산자이면 자식이 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
#include <iostream>
 
using namespace std;
 
int N;
bool answer;
 
bool isOper(char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/') return true;
    return false;
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        answer = true;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            char data;
            cin >> idx >> data;
 
            int cnt = 0;
            if (isOper(data)) cnt = 2;
            int childCnt = 0;
            while (getc(stdin) == ' ') {
                int trash;
                cin >> trash;
                childCnt++;
            }
            if (childCnt != cnt) answer = false;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

자료구조 트리에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 5656 - 벽돌 깨기(2)  (0) 2023.01.02
[C++] SWEA 1232 - 사칙연산  (1) 2022.12.31
[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE&problemTitle=1231&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 트리 정보를 입력받는다.

2. 트리를 중위순회해서 얻은 문자열을 출력한다.

 

<해법>

1. 트리 정보 저장 방법

=> 문제에서 트리는 완전 이진탐색으로 주어집니다. 따라서, 배열로 구현할 수 있고 각 노드의 자식들은 (본인 index * 2), (본인 index * 2 + 1)로 나타낼 수 있습니다.(루트노드를 index 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <string.h>
 
using namespace std;
 
int N;
char tree[101];
string answer;
 
string inOrderSearch(int idx) {
    if (idx > N) return "";
 
    string ret = "";
    ret = inOrderSearch(idx * 2) + tree[idx] + inOrderSearch((idx * 2) + 1);
    return ret;
}
 
void solution() {
    answer = inOrderSearch(1);
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        memset(tree, NULL, sizeof(tree));
        answer = "";
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            char c;
            cin >> idx >> c;
            tree[idx] = c;
 
            int trash;
            while (getc(stdin) == ' ') {
                cin >> trash;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

중위순회에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 1232 - 사칙연산  (1) 2022.12.31
[C++] SWEA 1233 - 사칙연산 유효성 검사  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 암호문과 명령어를 입력받는다.

2. 암호문을 명령어에 맞게 수정하고, 암호문의 처음 10개의 숫자를 출력한다.

 

<해법>

1. 자료구조 선택하기

=> 저는 list 자료구조를 선택하였습니다. I 명령어는 list의 splice를, D는 erase를, A는 push_back를 사용하여 구현하였습니다.

 

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
#include <iostream>
#include <list>
 
using namespace std;
 
int N;
list<int> code;
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        code.clear();
 
        //입력 및 해법
        cin >> N;
        for (int i = 0; i < N; i++) {
            int num = 0;
            cin >> num;
            code.push_back(num);
        }
        cin >> N;
        for (int i = 0; i < N; i++) {
            char cmd;
            int x, y, s;
            cin >> cmd;
            if (cmd == 'I') {
                cin >> x >> y;
                list<int> add;
                for (int j = 0; j < y; j++) {
                    cin >> s;
                    add.push_back(s);
                }
                auto iter = code.begin();
                while (x--) iter++;
                code.splice(iter, add);
            }
            else if (cmd == 'D') {
                cin >> x >> y;
                auto iter = code.begin();
                while (x--) iter++;
                while (y--) {
                    iter = code.erase(iter);
                }
            }
            else {
                cin >> y;
                for (int j = 0; j < y; j++) {
                    cin >> s;
                    code.push_back(s);
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " ";
        for (int i = 0; i < 10; i++) {
            cout << code.front() << " ";
            code.pop_front();
        }
        cout << "\n";
    }
 
    //종료
    return 0;
}

 

리스트 자료구조에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 1233 - 사칙연산 유효성 검사  (0) 2022.12.31
[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 5644 - 무선 충전(2)  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24
[C++] SWEA 1225 - 암호생성기  (0) 2022.12.24

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=5644&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 배터리 BC 정보와 사용자 이동 정보를 입력받는다.

2. 사용자가 충전한 양의 합의 최댓값을 출력한다.

 

<해법>

1. 사용자가 충전한 양의 합이 최대가 되는 BC 선택하기

=> 사용자 한명씩 모두 BC를 선택해보아야 합니다. 따라서, 저는 재귀함수를 이용해서 브루트포스를 구현하였습니다.

 

2. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 주어진 사용자 이동 정보를 이용해 시뮬레이션을 진행한다.

(2) 사용자가 이동할 때마다, 재귀함수를 이용해 충전한 양의 최댓값을 구한다.

(3) 충전한 양의 합을 출력한다.

자세한 구현은 아래 코드를 참조해주세요.

 

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
#include <iostream>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
struct bc {
    pos p;
    int c;
    int power;
};
 
int dx[] = { 0,-1,0,1,0 };
int dy[] = { 0,0,1,0,-1 };
 
int M, A;
int dir[2][101];
bc BC[8];
pos user[2];
bool visited[8];
int answer;
 
bool canCharge(pos p, int num) {
    if (abs(p.x - BC[num].p.x) + abs(p.y - BC[num].p.y) <= BC[num].c) return true;
    return false;
}
 
int chargeAmount(int idx) {
    if (idx == 2) return 0;
 
    int ret = 0;
    for (int i = 0; i < A; i++) {
        if (canCharge(user[idx], i) && !visited[i]) {
            visited[i] = true;
            ret = max(ret, chargeAmount(idx + 1) + BC[i].power);
            visited[i] = false;
        }
    }
    ret = max(ret, chargeAmount(idx + 1));
    return ret;
}
 
int simulation() {
    int output = 0;
    user[0].x = 1, user[0].y = 1, user[1].x = 10, user[1].y = 10;
    
    for (int time = 0; time <= M; time++) {
        for (int i = 0; i < 2; i++) {
            user[i].x += dx[dir[i][time]];
            user[i].y += dy[dir[i][time]];
        }
        output += chargeAmount(0);
    }
   
    return output;
}
 
void solution() {
    answer = simulation();
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        M = 0, A = 0;
        memset(dir, 0, sizeof(dir));
        for (int i = 0; i < 8; i++) {
            BC[i] = { 0,0,0,0 };
        }
        for (int i = 0; i < 2; i++) {
            user[i] = { 0,0 };
        }
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> M >> A;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= M; j++) {
                cin >> dir[i][j];
            }
        }
        for (int i = 0; i < A; i++) {
            int x = 0, y = 0, c = 0, power = 0;
            cin >> y >> x >> c >> power;
            BC[i] = { {x,y},c,power };
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

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

저작자표시

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

[C++] SWEA 1231 - 중위순회  (0) 2022.12.31
[C++] SWEA 1230 - 암호문3  (0) 2022.12.24
[C++] SWEA 1227 - 미로2  (0) 2022.12.24
[C++] SWEA 1225 - 암호생성기  (0) 2022.12.24
[C++] SWEA 5650 - 핀볼 게임(2)  (0) 2022.12.23

+ Recent posts

티스토리툴바