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

 

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
#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int N, B;
int H[20];
int answer;
 
void makeTower(int index, int sumHeight) {
 
    //종료조건
    if (index == N) {
        if (sumHeight >= B) {
            //결과 갱신
            answer = min(answer, sumHeight);
        }
        return;
    }
 
    //현재 탑을 쌓는 경우 해보기
    makeTower(index + 1, sumHeight + H[index]);
 
    //현재 탑을 쌓지 않는 경우 해보기
    makeTower(index + 1, sumHeight);
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, B = 0;
        memset(H, 0, sizeof(H));
        answer = INF;
 
        //입력
        cin >> N >> B;
        for (int i = 0; i < N; i++) {
            cin >> H[i];
        }
 
        //해법
        makeTower(0, 0);
 
        //출력
        cout << "#" << test_case << " " << answer - B << "\n";
    }
 
    //종료
    return 0;
}
 

 

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

저작자표시

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

[C++] SWEA 5653 - 줄기세포배양  (0) 2022.11.29
[C++] SWEA 2115 - 벌꿀채취  (0) 2022.11.28
[C++] SWEA 1861 - 정사각형 방  (0) 2021.01.21
[C++] SWEA 4408 - 자기 방으로 돌아가기  (0) 2021.01.17
[C++] SWEA 3752 - 가능한 시험 점수  (0) 2021.01.13

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 방 정보를 입력받는다.

2. 방을 최대로 이동할 수 있을 때의 방 숫자와, 그 때 이동한 방 개수를 출력한다.

 

<해법>

1. 이동한 방 개수를 구하는 방법

=> 이동한 방 개수를 구하는 방법은 굉장히 간단합니다. 각 좌표마다 방을 이동할 수 있을때까지 이동하고, 총 개수를 구합니다. 하지만 여기서 조금 더 생각하면 중복을 제거할 수 있는 원리가 보입니다.

위 그림과 같이 4번 방에서 이동할 수 있는 방의 개수는 (1+3번 방에서 이동할 수 있는 방의 개수) 입니다.

따라서, 위 점화식을 사용하여 DP로 접근하면 중복을 제거할 수 있습니다.

 

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 <string.h>
#include <algorithm>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
//4방향 : 북, 동, 남, 서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int map[1000][1000];
int cache[1000][1000]; //DP 저장 배열
int N;
int Answer_RoomNum;
int Answer_RoomCnt;
 
//현재 좌표가 범위 안에 있는지 판단
bool isInner(pos p) {
    if (p.x < 0 || p.y < 0 || p.x >= N || p.y >= N) {
        return false;
    }
    return true;
}
 
//현재 좌표에서 다음 좌표로 이동할 수 있는지 판단
bool canGo(pos cur, pos nxt) {
    if (map[cur.x][cur.y] + 1 == map[nxt.x][nxt.y]) {
        return true;
    }
    return false;
}
 
//DP 풀이
int move(pos cur) {
 
    int& ret = cache[cur.x][cur.y];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = 1;
 
    for (int i = 0; i < 4; i++) {
        pos nxt = cur;
        nxt.x += di[i];
        nxt.y += dj[i];
 
        if (!isInner(nxt)) {
            continue;
        }
 
        if (canGo(cur, nxt)) {
 
            /*
            현재 좌표에서 이동할 수 있는 방의 수 = 1 + 다음 좌표에서 이동할 수 있는 방의 수
            */
            ret += move(nxt);
        }
    }
 
    return ret;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        memset(cache, -1, sizeof(cache));
        N = 0;
        Answer_RoomNum = 0, Answer_RoomCnt = 0;
 
        //입력
        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++) {
 
                //{i, j}에서 이동할 수 있는 방의 개수 구하기
                int Tmp_RoomCnt = move({ i, j });
 
                //결과 갱신
                if (Tmp_RoomCnt > Answer_RoomCnt) {
                    Answer_RoomCnt = Tmp_RoomCnt;
                    Answer_RoomNum = map[i][j];
                }
                else if (Tmp_RoomCnt == Answer_RoomCnt) {
                    Answer_RoomNum = min(Answer_RoomNum, map[i][j]);
                }
            }
        }
 
        //결과 출력
        cout << "#" << test_case << " " << Answer_RoomNum << " " << Answer_RoomCnt << "\n";
    }
 
    //종료
    return 0;
}
 

 

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

저작자표시

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

[C++] SWEA 2115 - 벌꿀채취  (0) 2022.11.28
[C++] SWEA 1486 - 장훈이의 높은 선반  (0) 2021.01.21
[C++] SWEA 4408 - 자기 방으로 돌아가기  (0) 2021.01.17
[C++] SWEA 3752 - 가능한 시험 점수  (0) 2021.01.13
[C++] SWEA 2814 - 최장 경로  (0) 2021.01.12

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

 

코딩테스트 연습 - [3차] 압축

TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]

programmers.co.kr

<풀이>

1. 문자열을 주어진 LZW 압축 과정에 따라 압축한다.

2. 압축이 모두 완료된 후, 색인 번호들을 반환한다.

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않습니다. 주어진 LZW 압축 과정을 정확하게 구현하는 것이 문제의 핵심이라고 생각합니다. 저는 주어진 압축 과정을 최대한 똑같이 구현하는데 초점을 두어서 구현하였습니다.

 

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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
//사전
vector<string> dict;
 
//메시지 안에 같은 단어가 있는지 확인
bool hasSameVocab(string msg, string vocab) {
 
    for (int i = 0; i < vocab.length(); i++) {
        if (vocab[i] != msg[i]) {
            return false;
        }
    }
 
    return true;
}
 
vector<int> solution(string msg) {
    vector<int> answer;
 
    /*
    1. 사전 만들기
    */
    dict.push_back("#");
    for (int i = 0; i < 26; i++) {
        char alpha = 'A' + i;
        dict.push_back(string(1, alpha));
    }
 
    /*
    2번 ~ 5번 반복
    */
    while (true) {
 
        /*
        2. 사전에서 입력과 일치하는 가장 긴 문자열 찾기
        */
        string removeVocab = ""; //지워지는 단어
        int index; //사전 색인
 
        //사전을 모두 탐색
        for (int i = 1; i < dict.size(); i++) {
 
            string vocab = dict[i];
 
            //메시지안에 같은 단어가 있고, 길이가 더 긴 단어 지우기
            if (hasSameVocab(msg, vocab) && vocab.length() > removeVocab.length()) {
                removeVocab = vocab;
                index = i;
            }
        }
 
        /*
        3. 색인 번호 담고, 메시지에서 해당 단어 지우기
        */
        answer.push_back(index);
        msg = msg.substr(removeVocab.length());
 
        /*
        4. 다음 글자가 남아 있을 경우, 다음 글자 포함해서 사전 등록
        */
        if (msg.empty()) {
            break;
        }
        else {
            dict.push_back(removeVocab + msg[0]);
        }
    }
 
    //결과 반환
    return answer;
}
 

 

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

저작자표시

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

[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16

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

 

코딩테스트 연습 - [3차] 방금그곡

방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV,

programmers.co.kr

<풀이>

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
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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//구조체 : 음악 정보
struct music {
    int index;
    int time;
    string title;
};
 
vector<music> v;
 
//멜로디 변환 함수('#' 없애기)
string changeMelody(string s) {
 
    while (true) {
 
        //'#'을 찾기
        int index = s.find("#");
 
        //'#'이 없으면 종료
        if (index == string::npos) {
            break;
        }
 
        //'#'이 있으면, '#'전에 있는 알파벳 소문자로 변환
        char alpha = tolower(s[index - 1]);
 
        //소문자 알파벳으로 바꾸기(ex. C# -> c)
        s.replace(index - 1, 2, string(1, alpha));
    }
 
    return s;
}
 
//벡터 정렬 기준
bool compare(music a, music b) {
    if (a.time == b.time) {
        return a.index < b.index;
    }
    return a.time > b.time;
}
 
string solution(string m, vector<string> musicinfos) {
 
    string answer = "";
 
    //네오가 기억한 멜로디 -> '#'없앤 멜로디로 변환
    string neoMelody = changeMelody(m);
 
    //주어진 음악 정보 탐색
    for (int i = 0; i < musicinfos.size(); i++) {
 
        /*
        1. 시간 정보 탐색
        */
        string timeInfo = musicinfos[i].substr(0, 11);
 
        int start_time = stoi(timeInfo.substr(0, 2)) * 60 + stoi(timeInfo.substr(3, 2));
        int finish_time = stoi(timeInfo.substr(6, 2)) * 60 + stoi(timeInfo.substr(9, 2));
 
        //총 소요시간
        int time = finish_time - start_time;
 
        /*
        2. 제목, 멜로디 정보 탐색
        */
        string musicInfo = musicinfos[i].substr(12);
 
        //',' 위치 찾기
        int comma_pos = musicInfo.find(',');
 
        //',' 위치를 기준으로 제목, 멜로디 정보 찾기
        string title = musicInfo.substr(0, comma_pos);
        string melody = musicInfo.substr(comma_pos + 1);
 
        /*
        3. 소요시간만큼 진행된 멜로디 구하기
        */
        //멜로디 변환
        melody = changeMelody(melody);
 
        string totalMelody = "";
 
        //멜로디 길이 >= 소요시간
        if (melody.length() >= time) {
            totalMelody = melody.substr(0, time);
        }
        //멜로디 길이 < 소요시간
        else {
 
            //몫만큼 멜로디를 반복
            int repeatCount = time / melody.length();
            for (int j = 0; j < repeatCount; j++) {
                totalMelody += melody;
            }
 
            //나머지 시간, 나머지 멜로디
            int remain = time % melody.length();
            totalMelody += melody.substr(0, remain);
        }
 
        /*
        4. 토탈 멜로디에서 네오 멜로디 찾기
        */
        int index = totalMelody.find(neoMelody);
 
        //멜로디를 찾은 경우 벡터에 저장
        if (index != string::npos) {
            v.push_back({ i, time, title });
        }
    }
 
    //찾은 멜로디 정렬
    sort(v.begin(), v.end(), compare);
 
    //결과 갱신
    if (v.empty()) {
        answer = "(None)";
    }
    else {
        answer = v[0].title;
    }
 
    //결과 반환
    return answer;
}
 

 

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

저작자표시

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

[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11

www.acmicpc.net/problem/1074

 

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서

www.acmicpc.net

<풀이>

1. N, r, c를 입력받는다.

2. 주어진 규칙에 따라 Z를 그려가면서, r행 c열에 방문한 번째를 구하고 출력한다.

 

<해법>

1. 방문한 번째를 구하는 방법

=> 저는 항상 문제를 풀 때, 프로그래밍 문제가 아니라고 생각하고 접근합니다. '내가 그냥 푼다면 어떻게 풀까?'

이 문제를 그냥 풀 때 빠르게 풀 수 있는 핵심은, 그려볼 필요 없는 Z는 그리지 않고 계산을 통해 구하는 것 입니다.

 

예를 들어서 설명해보겠습니다.

위와 같은 문제가 있을 때, 사람일 경우 어떻게 구할까요?

대부분의 사람이라면 빨간색 X부분은 Z를 그리지 않고, 빠르게 계산한 후에 (r, c)가 있는 부분을 탐색할 것입니다.

이제 문제를 모두 풀어보겠습니다.

이제 사람이 풀었던 방식을 컴퓨팅적인 방식으로 바꿔보겠습니다.

 

1. (r, c)가 해당 사각형에서 몇 분면에 있는지 파악한다.

2. (r, c)보다 이전에 있는 사분면들은 모두 빠르게 계산한다.

3. (r, c)가 있는 사분면을 탐색한다.

 

이렇게 바꿔볼 수 있고, 1~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
#include <iostream>
#include <math.h>
 
using namespace std;
 
int N, r, c;
int answer;
 
//(r,c)가 현재 사각형에서 몇사분면에 있는지 판단
int isInWhere(int x, int y, int n) {
 
    int position;
 
    //1사분면에 있을 경우
    if (r < x + n / 2 && c < y + n / 2) {
        position = 1;
    }
    //2사분면에 있을 경우
    else if (r < x + n / 2 && c < y + n) {
        position = 2;
    }
    //3사분면에 있을 경우
    else if (r < x + n && c < y + n / 2) {
        position = 3;
    }
    //4사분면에 있을 경우
    else {
        position = 4;
    }
 
    return position;
}
 
int makeZ(int x, int y, int n) {
 
    //정답 지점에 왔을 경우 -> 종료
    if (x == r && y == c) {
        return 0;
    }
 
    //한 변의 길이가 1인 경우 -> 종료
    if (n == 1) {
        return 1;
    }
    
    //해당 사각형에서 (r, c)가 몇사분면에 있는지 확인
    int position = isInWhere(x, y, n);
 
    //찾아야 하는 지점이 어디에 있는지에 따라서 더해야할 값이 다름
    if (position == 1) {
        return makeZ(x, y, n / 2);
    }
    else if (position == 2) {
        return (n / 2 * n / 2) + makeZ(x, y + n / 2, n / 2);
    }
    else if (position == 3) {
        return (n / 2 * n / 2) * 2 + makeZ(x + n / 2, y, n / 2);
    }
    else {
        return (n / 2 * n / 2) * 3 + makeZ(x + n / 2, y + n / 2, n / 2);
    }
}
 
int main() {
 
    //초기화
    N = 0, r = 0, c = 0;
    answer = 0;
 
    //입력
    cin >> N >> r >> c;
 
    //해법
    answer = makeZ(0, 0, pow(2, N));
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}
 

 

분할정복에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 2011 - 암호코드  (0) 2021.02.06
[C++] 백준 2156 - 포도주 시식  (0) 2021.01.25
[C++] 백준 1780 - 종이의 개수  (0) 2021.01.14
[C++] 백준 2447 - 별 찍기 10  (0) 2021.01.14
[C++] 백준 12100 - 2048(Easy)  (0) 2021.01.10

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

 

SW Expert Academy

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

swexpertacademy.com

<풀이>

1. 학생들의 현재 방과 돌아가야할 방 번호들을 입력받는다.

2. 학생들이 모두 이동하는데 걸리는 최소 시간을 출력한다.

 

<해법>

1. 최소 이동시간의 경우 이해하기

=> 가장먼저, 이동시간이 최소가 되는 경우가 언제인지 생각해 보아야합니다.

곰곰히 생각해보면, 한번에 학생들을 많이 움직여야 합니다. 그러기 위해서는 앞 번호 방부터 복도가 겹치지 않게해서 학생들을 많이 움직이게 해야합니다.

따라서, 저는 학생들의 방 정보를 현재 방 번호 크기 기준으로 정렬하였습니다.

 

2. 최소 이동시간 구하기

=> 정렬한 방 정보를 이용하여, 복도가 겹치지 않게 이동할 학생들을 정합니다. 이 때, 사용되는 복도를 유의해야합니다. 이 문제는 복도를 중앙에 두고 위, 아래로 방이 있습니다.

이 말은, 1 -> 3 방으로 가는 학생과 4 -> 6 방으로 가는 학생의 복도가 겹친다는 뜻 입니다.

따라서, 단순히 사용되는 복도를 설정할 때, 방의 숫자로만 하시면 안됩니다.

저는 위와 같은 경우를 해결하기 위해서, 1 -> 3 방으로 가는 학생을 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
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//구조체 : 방 정보
struct room {
    //시작 방 번호, 도착 방 번호
    int start, finish;
};
 
int N;
vector<room> v;
bool visited[400];
int answer;
 
//정렬 기준(시작 방 번호에 따라 정렬)
bool compare(room r1, room r2) {
    if (r1.start == r2.start) {
        return r1.finish < r2.finish;
    }
    return r1.start < r2.start;
}
 
bool allStudentReturn() {
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        v.clear();
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
 
            int room1, room2;
            cin >> room1 >> room2;
 
            //작은 번호 방에서 큰 번호 방으로 출발하도록 설정
            if (room1 > room2) {
                v.push_back({ room2, room1 });
            }
            else {
                v.push_back({ room1, room2 });
            }
        }
 
        //정렬(시작 방 번호가 작은 순서대로)
        sort(v.begin(), v.end(), compare);
 
        //시간 계산
        while (true) {
 
            //모든 학생이 방으로 돌아간 경우 -> 종료
            if (allStudentReturn()) {
                break;
            }
 
            int finish = 0;
 
            //모든 학생 점검
            for (int i = 0; i < N; i++) {
 
                //아직 방을 이동하지 못하였고 && 복도가 겹치지 않을 경우 -> 동시에 움직일 수 있음
                if (!visited[i] && v[i].start > finish) {
 
                    //방문 처리
                    visited[i] = true;
 
                    //방이 홀수인 경우 -> 쓰는 복도는 결국 방 번호가 짝수인 경우와 같다
                    if (v[i].finish % 2 == 1) {
                        finish = v[i].finish + 1;
                    }
                    else {
                        finish = v[i].finish;
                    }
                }
            }
 
            //시간 + 1
            answer++;
        }
 
        //결과 출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

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

저작자표시

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

[C++] SWEA 1486 - 장훈이의 높은 선반  (0) 2021.01.21
[C++] SWEA 1861 - 정사각형 방  (0) 2021.01.21
[C++] SWEA 3752 - 가능한 시험 점수  (0) 2021.01.13
[C++] SWEA 2814 - 최장 경로  (0) 2021.01.12
[C++] SWEA 2805 - 농작물 수확하기  (0) 2021.01.08

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

 

코딩테스트 연습 - [1차] 다트 게임

 

programmers.co.kr

<풀이>

1. 주어진 문자열에서 총 3게임의 점수를 구한다.

2. 각 1게임 마다 점수, 보너스, 옵션을 분리해서 해당 게임의 점수를 계산한다.

3. 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
#include <iostream>
#include <string>
 
using namespace std;
 
//3게임 점수
int scores[3];
 
int solution(string dartResult) {
    int answer = 0;
 
    //문자열 index
    int index = 0;
 
    //각 게임마다 점수 구하기
    for (int i = 0; i < 3; i++) {
 
        //1. 점수
        int score;
        if (dartResult[index] == '1' && dartResult[index + 1] == '0') { //점수가 10일 경우
            score = 10;
            index++;
        }
        else { //그 외
            score = dartResult[index] - '0';
        }
        scores[i] = score;
        index++;
 
        //2. 보너스
        char bonus;
        switch (dartResult[index]) {
        case 'S': scores[i] = scores[i] * 1; break;
        case 'D': scores[i] = scores[i] * scores[i]; break;
        case 'T': scores[i] = scores[i] * scores[i] * scores[i]; break;    
        }
        index++;
 
        //3. 옵션
        char option;      
        if (dartResult[index] == '*') {
            if (i != 0) { //첫 게임이 아닐 경우
                scores[i - 1] *= 2;
            }
            scores[i] *= 2;
        }
        else if (dartResult[index] == '#') {
            scores[i] *= -1;
        }
        else { //옵션이 없을 경우
            continue;
        }
        index++;
 
    }
 
    //점수 합계
    for (int i = 0; i < 3; i++) {
        answer += scores[i];
    }
 
    //결과 반환
    return answer;
}
 

 

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

저작자표시

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

[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 비밀지도  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11
[C++] 프로그래머스 - 프렌즈4블록  (0) 2021.01.07

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

 

코딩테스트 연습 - [1차] 비밀지도

비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다

programmers.co.kr

<풀이>

1. 두 개의 지도를 합쳐서 지도를 해독한다.

2. 해독한 지도를 반환한다.

 

<해법>

1. 지도를 합치는 방법

=> 저는 비트 연산자를 이용하였습니다. 주어지는 지도가 결국 2진수로 바꿔서 생각해야하는 걸 보면, 바꾸지 않고 비트연산자로 해결해야 겠다는 아이디어를 얻을 수 있었습니다.

 

2. 해독한 지도를 옮기는 방법

=> 비트 연산자를 통해 해독한 지도의 한 줄(10진수)을 알 수 있습니다. 이 숫자를 '#'과 ' '으로 나타내기 위해서는 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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
 
    vector<string> answer;
 
    for (int i = 0; i < n; i++) {
 
        //각 라인 숫자 OR(비트 연산자)로 구하기
        int line = arr1[i] | arr2[i];
 
        string str = "";
 
        //10진법 -> 2진법으로 바꾸기
        for (int j = 0; j < n; j++) {
 
            if (line % 2 == 1) {
                str = "#" + str;
            }
            else {
                str = " " + str;
            }
 
            line = line / 2;
        }
 
        //결과 갱신
        answer.push_back(str);
    }
 
    //결과 반환
    return answer;
}
 

 

비트 연산자와 진법에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16
[C++] 프로그래머스 - 캐시  (0) 2021.01.11
[C++] 프로그래머스 - 프렌즈4블록  (0) 2021.01.07
[C++] 프로그래머스 - 셔틀버스  (0) 2021.01.04

+ Recent posts

티스토리툴바