'알고리즘 문제풀이/SWEA' 카테고리의 글 목록 (3 Page)

알고리즘 문제풀이/SWEA

[C++] SWEA 1215 - 회문1(2)

2022. 12. 15. 16:32

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

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

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

2. 글자판에서 주어진 길이의 회문 개수를 출력한다.

<해법>

1. 회문인지 판별하는 방법

=> 그림으로 대체 하겠습니다. 구현은 코드의 isPalindrome을 참조해 주시면 됩니다.

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

#include <iostream>
#include <string.h>
 
using namespace std;
 
int pLength;
char map[8][8];
int answer;
 
bool isPalindrome(string str) {
    int start = 0;
    int end = str.length() - 1;
    for (int i = 0; i < str.length() / 2; i++) {
        if (str[start + i] != str[end - i]) return false;
    }
    return true;
}
 
void solution() {
 
    string str = "";
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (j + pLength <= 8) {
                str = "";
                for (int k = 0; k < pLength; k++) {
                    str += map[i][j + k];
                }
                if (isPalindrome(str)) answer++;
            }
 
            if (i + pLength <= 8) {
                str = "";
                for (int k = 0; k < pLength; k++) {
                    str += map[i + k][j];
                }
                if (isPalindrome(str)) answer++;
            }
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        pLength = 0;
        memset(map, '0', sizeof(map));
        answer = 0;
 
        //입력
        cin >> pLength;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        solution();
        
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

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

저작자표시

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

[C++] SWEA 1217 - 거듭 제곱 (0)	2022.12.21
[C++] SWEA 1216 - 회문2 (0)	2022.12.15
[C++] SWEA 1213 - String (0)	2022.12.15
[C++] SWEA 1953 - 탈주범 검거(2) (0)	2022.12.15
[C++] SWEA 1949 - 등산로 조정 (0)	2022.12.15

[C++] SWEA 1213 - String

2022. 12. 15. 16:11

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. pattern과 text를 입력받는다.

2. text내에 있는 pattern의 개수를 출력한다.

<해법>

1. 문제를 해결하는 흐름

(1) 문자열에서 가장 빨리 나타나는 pattern을 찾습니다.

(2) 문자열을 pattern 뒤부터로 갱신합니다.

예를 들어, text가 "abcde..."이고 pattern이 "bc"라고 하겠습니다. text내에서 가장빨리 나타나는 패턴을 찾으면 a[bc]de... 입니다. 이후, text를 d...로 교체합니다.

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

#include <iostream>
#include <string>
 
using namespace std;
 
int trash;
string text;
string pattern;
int answer;
 
void solution() {
    int index = 0;
    while (true) {
        index = text.find(pattern, index);
 
        if (index == string::npos) {
            break;
        }
 
        index += pattern.length();
        answer++;
    }
}
 
int main() {
    int test_case;
    int T;
 
    T = 10;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        trash = 0;
        text = "";
        pattern = "";
        answer = 0;
 
        //입력
        cin >> trash >> pattern >> text;
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

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

저작자표시

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

[C++] SWEA 1216 - 회문2 (0)	2022.12.15
[C++] SWEA 1215 - 회문1(2) (0)	2022.12.15
[C++] SWEA 1953 - 탈주범 검거(2) (0)	2022.12.15
[C++] SWEA 1949 - 등산로 조정 (0)	2022.12.15
[C++] SWEA 4311 - 오래된 스마트폰 (0)	2022.12.07

[C++] SWEA 1953 - 탈주범 검거(2)

2022. 12. 15. 15:48

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

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 지하터널 지도를 입력받는다.

2. 주어진 시간동안 탈주범이 위치할 수 있는 장소의 개수를 출력한다.

<해법>

1. 문제를 해결한 핵심 알고리즘

=> 저는 먼저 문제를 간단히 생각해보았습니다. 터널 구조물이 없다고 생각하면, 단순한 길찾기 문제입니다. 문제가 주어진 시간동안 점차 움직이는 것이므로, DFS보다는 BFS를 선택하는 것이 적합하다고 생각하였습니다. 저는 BFS를 이용하여 해결하였습니다.

2. 다른 터널 구조물로 갈 수 있는지 판단하는 방법

=> 다음은 터널 구조물을 처리하는 방법입니다. 현재 내가 있는 터널 구조물을 1번이라고 하고, 그 위에 있는 구조물을 2번이라고 하겠습니다. 1번과 2번끼리 연결되어있는지 알아보려면, (1) 1번 구조물이 위로 갈 수 있어야한다. 와 (2) 2번 구조물은 아래(위와 반대방향)로 갈 수 있어야한다. 입니다. 저는 모든 구조물마다 갈 수 있는 방향을 미리 배열로 저장해 두었습니다. 자세한건 아래 코드의 type배열을 참조하시면 됩니다.

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

#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int type[8][4] = {
    {0,0,0,0},
    {1,1,1,1}, //1번 구조물
    {1,0,1,0}, //2번 구조물
    {0,1,0,1}, //...
    {1,1,0,0},
    {0,1,1,0}, 
    {0,0,1,1},
    {1,0,0,1}
};
 
int N, M, R, C, L;
int map[50][50];
bool visited[50][50];
int answer;
 
bool isInner(pos p) {
    if (p.x < 0 || p.y < 0 || p.x >= N || p.y >= M) {
        return false;
    }
    return true;
}
 
bool canConnect(int from, int to, int dir) {
    if (type[from][dir] && type[to][(dir + 2) % 4]) return true;
    return false;
}
 
void solution() {
    queue<pos> q;
    q.push({ R,C });
    visited[R][C] = true;
    while (L && !q.empty()) {
        int qsize = q.size();
        while (qsize--) {
            pos cur = q.front();
            q.pop();
            answer++;
 
            for (int i = 0; i < 4; i++) {
                pos nxt = cur;
                nxt.x += dx[i];
                nxt.y += dy[i];
 
                if (!isInner(nxt) || visited[nxt.x][nxt.y]) continue;
 
                if (canConnect(map[cur.x][cur.y], map[nxt.x][nxt.y], i)) {
                    visited[nxt.x][nxt.y] = true;
                    q.push(nxt);
                }
            }
        }
        L--;
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0, R = 0, C = 0, L = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N >> M >> R >> C >> L;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

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

저작자표시

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

[C++] SWEA 1215 - 회문1(2) (0)	2022.12.15
[C++] SWEA 1213 - String (0)	2022.12.15
[C++] SWEA 1949 - 등산로 조정 (0)	2022.12.15
[C++] SWEA 4311 - 오래된 스마트폰 (0)	2022.12.07
[C++] SWEA 5658 - 보물상자 비밀번호 (0)	2022.12.06

[C++] SWEA 1949 - 등산로 조정

2022. 12. 15. 12:03

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 가장 높은 봉우리에서 시작해서 등산로를 찾습니다.

2. 만들 수 있는 등산로 중 가장 긴 등산로를 찾고 그 길이를 출력한다.

<해법>

1. 문제를 해결한 핵심 알고리즘

=> 지형을 깎는다는 조건이 없다면, 제일 높은 봉우리에서 사방을 찾아가며 내려가는 문제입니다. 저는 문제를 읽고 DFS가 떠올랐습니다.

2. 봉우리를 깎는 방법

=> 봉우리는 1~K만큼 깎을 수 있습니다. 하지만, 1~K만큼 모두 깎아볼 필요는 없습니다. 가장 길게 만들 수 있는 등산로를 찾는 문제이기 때문에, 현재 높이보다 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

#include <iostream>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, K;
int map[8][8];
bool visited[8][8];
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    return true;
}
 
int findRoute(int x, int y, bool cut) {
 
    int ret = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (!isInner(nx, ny) || visited[nx][ny]) continue;
 
        if (map[nx][ny] < map[x][y]) {
            visited[nx][ny] = true;
            ret = max(ret, findRoute(nx, ny, cut) + 1);
            visited[nx][ny] = false;
        }
        else {
            if (!cut && map[nx][ny] - K < map[x][y]) {
                int tmp = map[nx][ny];
                map[nx][ny] = map[x][y] - 1; //현재 지형보다 1만큼만 낮게 깎음
                visited[nx][ny] = true;
                ret = max(ret, findRoute(nx, ny, 1) + 1);
                map[nx][ny] = tmp;
                visited[nx][ny] = false;
            }
        }
    }
 
    return ret;
}
 
void solution() {
    //1. 가장 높은 봉우리 찾기
    int peek = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] > peek) {
                peek = map[i][j];
            }
        }
    }
 
    //2. 가장 높은 봉우리에서 등산로 찾기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == peek) {
                visited[i][j] = true;
                answer = max(answer, findRoute(i, j, false));
                visited[i][j] = false;
            }
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, K = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N >> K;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

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

저작자표시

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

[C++] SWEA 1213 - String (0)	2022.12.15
[C++] SWEA 1953 - 탈주범 검거(2) (0)	2022.12.15
[C++] SWEA 4311 - 오래된 스마트폰 (0)	2022.12.07
[C++] SWEA 5658 - 보물상자 비밀번호 (0)	2022.12.06
[C++] SWEA 2105 - 디저트 카페 (0)	2022.12.06

[C++] SWEA 4311 - 오래된 스마트폰

2022. 12. 7. 10:12

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 스마트폰 정보를 입력받는다.

2. 주어진 스마트폰으로 W를 만들 수 있는 최소 터치 횟수를 출력한다.

<해법>

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
121
122

//라이브러리 사용 불가
#include <iostream>
#define INF 987654321
 
using namespace std;
 
int N, O, M, W;
int numPad[10];
int operPad[4];
int nums[1000];
int numsSize;
int bestTouchCnt[1000];
int answer;
 
//연산
int calculate(int oper, int n1, int n2) {
    int output = 0;
    switch (oper) {
    case 1:
        output = n1 + n2;
        break;
    case 2:
        output = n1 - n2;
        break;
    case 3:
        output = n1 * n2;
        break;
    case 4:
        if (n2 == 0) return -1;
        output = n1 / n2;
        break;
    }
 
    return (0 <= output && output <= 999) ? output : -1;
}
 
//연산자 없이 숫자 만들기
void makeNum(int select, int num) {
 
    if (select == min(M, 3)) return; 
 
    for (int i = 0; i < N; i++) {
        int nxtNum = num * 10 + numPad[i];
        if (bestTouchCnt[nxtNum] <= select + 1) continue;
        bestTouchCnt[nxtNum] = select + 1;
        makeNum(select + 1, nxtNum);
    }
}
 
//연산자 이용해서 숫자 만들기
void makeNumWithOper(int n1, int touchCnt) {
 
    if (n1 == W) return;
 
    for (int i = 0; i < numsSize; i++) {
        int n2 = nums[i];
        int nxtTouchCnt = bestTouchCnt[n1] + bestTouchCnt[n2] + 1;
 
        if (nxtTouchCnt + 1 > M) continue;
 
        for (int j = 0; j < O; j++) {
            int oper = operPad[j];
            int nxtNum = calculate(oper, n1, n2);
            if (nxtNum == -1 || bestTouchCnt[nxtNum] <= nxtTouchCnt) continue;
            bestTouchCnt[nxtNum] = nxtTouchCnt;
            makeNumWithOper(nxtNum, nxtTouchCnt);
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, O = 0, M = 0, W = 0;
        for (int i = 0; i < 10; i++) numPad[i] = 0;
        for (int i = 0; i < 4; i++) operPad[i] = 0;
        for (int i = 0; i < 1000; i++) nums[i] = 0;
        numsSize = 0;
        for (int i = 0; i < 1000; i++) bestTouchCnt[i] = INF;
        answer = 0;
 
        //입력
        cin >> N >> O >> M;
        for (int i = 0; i < N; i++) {
            cin >> numPad[i];
        }
        for (int i = 0; i < O; i++) {
            cin >> operPad[i];
        }
        cin >> W;
 
        /* 해법 */
        //1. 연산자 없이 모든 숫자를 만든다.
        makeNum(0, 0);
 
        //2. (1) 연산자 없이 W를 만들 수 있으면, 바로 정답 갱신
        //   (2) 연산자 없이 못 만들면, 연산자를 이용해보고 정답 갱신
        if (bestTouchCnt[W] != INF) answer = bestTouchCnt[W];
        else {
            for (int i = 0; i < 1000; i++) {
                if (bestTouchCnt[i] != INF) nums[numsSize++] = i;
            }
            for (int i = 0; i < numsSize; i++) {
                int n1 = nums[i];
                makeNumWithOper(n1, bestTouchCnt[n1]);
            }
            answer = (bestTouchCnt[W] == INF) ? -1 : bestTouchCnt[W] + 1;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

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

저작자표시

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

[C++] SWEA 1953 - 탈주범 검거(2) (0)	2022.12.15
[C++] SWEA 1949 - 등산로 조정 (0)	2022.12.15
[C++] SWEA 5658 - 보물상자 비밀번호 (0)	2022.12.06
[C++] SWEA 2105 - 디저트 카페 (0)	2022.12.06
[C++] SWEA 1952 - 수영장 (0)	2022.12.06

[C++] SWEA 5658 - 보물상자 비밀번호

2022. 12. 6. 20:53

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 보물상자에 적힌 숫자를 입력받는다.

2. 보물상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 구하고 출력한다.

<해법>

1. 숫자를 만드는 방법

=> 슬라이딩 윈도우 알고리즘을 이용합니다. index를 편하게 관리하기 위해서, 뚜껑 문자열을 두 개 연달아 이어붙입니다.

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 <set>
 
using namespace std;
 
//16진수를 10진수로 바꾸는 함수
long long convertHexToDec(string str) {
    long long output = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] >= 'A' && str[i] <= 'F') {
            output = output * 16 + str[i] - 'A' + 10;
        }
        else {
            output = output * 16 + str[i] - '0';
        }
    }
    return output;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        int N = 0, K = 0;
        string cover = "";
        set<string, greater<>> s;
        long long answer = 0;
 
        //입력
        cin >> N >> K;
        cin >> cover;
 
        /* 해법 */
        //1. 가능한 모든 비밀번호를 set에 담음(슬라이딩 윈도우 이용)
        int passwordLength = N / 4;
        cover += cover;
        for (int i = 0; i < N; i++) {
            s.insert(cover.substr(i, passwordLength));
        }
 
        //2. K번째 수 저장
        int count = 1;
        for (string password : s) {
            if (count == K) {
                answer = convertHexToDec(password);
                break;
            }
            count++;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

슬라이딩 윈도우와 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 1949 - 등산로 조정 (0)	2022.12.15
[C++] SWEA 4311 - 오래된 스마트폰 (0)	2022.12.07
[C++] SWEA 2105 - 디저트 카페 (0)	2022.12.06
[C++] SWEA 1952 - 수영장 (0)	2022.12.06
[C++] SWEA 4014 - 활주로 건설 (0)	2022.12.06

[C++] SWEA 2105 - 디저트 카페

2022. 12. 6. 17:47

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 디저트 카페 지역을 입력받는다.

2. 디저트를 가장 많이 먹을 수 있는 경로의 디저트 수를 출력한다.

<해법>

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

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dx[] = {-1, 1, 1, -1};
int dy[] = {1, 1, -1, -1};
int N;
int map[20][20];
bool visited[101];
int startX, startY;
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    return true;
}
 
void eatDessert(int x, int y, int dir, int count) {
 
    //방향 초과 -> 종료
    if (dir > 3) return;
 
    int nx = x + dx[dir];
    int ny = y + dy[dir];
 
    //직사각형 완료 -> 정답 갱신 후 종료
    if (nx == startX && ny == startY && dir == 3) {
        answer = max(answer, count);
        return;
    }
 
    //범위를 벗어난 경우 or 해당 디저트를 먹은 경우 -> 종료
    if (!isInner(nx, ny) || visited[map[nx][ny]]) return;
 
    visited[map[nx][ny]] = true;
    eatDessert(nx, ny, dir, count + 1);        //현재 방향 유지
    eatDessert(nx, ny, dir + 1, count + 1);    //다음 방향 꺾기
    visited[map[nx][ny]] = false;
}
 
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));
        memset(visited, false, sizeof(visited));
        startX = 0, startY = 0;
        answer = -1;
 
        //입력
        cin >> N;
        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++) {
                visited[map[i][j]] = true;
                startX = i, startY = j;
                eatDessert(i, j, 0, 1);
                visited[map[i][j]] = false;
            }
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

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

저작자표시

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

[C++] SWEA 4311 - 오래된 스마트폰 (0)	2022.12.07
[C++] SWEA 5658 - 보물상자 비밀번호 (0)	2022.12.06
[C++] SWEA 1952 - 수영장 (0)	2022.12.06
[C++] SWEA 4014 - 활주로 건설 (0)	2022.12.06
[C++] SWEA 4012 - 요리사 (0)	2022.12.06

[C++] SWEA 1952 - 수영장

2022. 12. 6. 17:15

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

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 수영장 이용계획을 입력받는다.

2. 수영장 이용비용의 최소금액을 구해 출력한다.

<해법>

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

#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int prices[4];
int calendar[12];
int cache[12];
 
int buyTicket(int month) {
 
    //종료조건
    if (month >= 12) {
        return 0;
    }
 
    //해당 달에 이용이 없는 경우 -> 다음 달로 넘김
    if (calendar[month] == 0) {
        return buyTicket(month + 1);
    }
 
    //메모이제이션
    int& ret = cache[month];
 
    if (cache[month] != -1) {
        return ret;
    }
 
    ret = min({
        buyTicket(month + 1) + (prices[0] * calendar[month]),
        buyTicket(month + 1) + prices[1],
        buyTicket(month + 3) + prices[2],
        buyTicket(month + 12) + prices[3]
    });
 
    return ret;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(prices, 0, sizeof(prices));
        memset(calendar, 0, sizeof(calendar));
        memset(cache, -1, sizeof(cache));
        int answer = 0;
 
        //입력
        for (int i = 0; i < 4; i++) {
            cin >> prices[i];
        }
        for (int i = 0; i < 12; i++) {
            cin >> calendar[i];
        }
 
        //해법
        answer = buyTicket(0);
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

재귀함수와 메모이제이션에 대해서 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] SWEA 5658 - 보물상자 비밀번호 (0)	2022.12.06
[C++] SWEA 2105 - 디저트 카페 (0)	2022.12.06
[C++] SWEA 4014 - 활주로 건설 (0)	2022.12.06
[C++] SWEA 4012 - 요리사 (0)	2022.12.06
[C++] SWEA 5648 - 원자 소멸 시뮬레이션 (0)	2022.12.05

PREV 1 2 3 4 5 6 ···8 NEXT

알고리즘 고수가 되기까지