Hwan. 001

문제

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

접근 방식

• 지도 공간 중의 0인 위치를 찾아, 중복 되지 않고 3개의 위치를 선택한다. (순열)
• 해당 위치에 벽을 세우고 BFS로 바이러스를 확산시킨다. (4 방향)
• 모든 지도에 수행하면서 안전한 영역(0인 곳)이 가장 많이 남은 개수를 찾는다.

코드

#include <iostream>
#include <queue> 
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility> 

using namespace std;

void func_14502_virusInfect(int n, int m, int **_map, queue<pair<int, int>> q) {
	pair<int, int> cur;
	int _x, _y;
	int direc[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

	while (!q.empty()) {
		cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			_x = cur.first + direc[i][0];
			_y = cur.second + direc[i][1];

			if (_x >= n || _x < 0)
				continue;
            
			if (_y >= m || _y < 0)
				continue;

			if (_map[_x][_y] == 1 || _map[_x][_y] == 2) {
				continue;
			}

			_map[_x][_y] = 2;
			q.push({_x, _y});
		}
	}
}

int main() {
	int n, m, cnt, max_safeZone = 0;

	vector<pair<int, int>> _map_v;
	queue<pair<int, int>> q;

	cin >> n >> m;
	
	int** _map = new int* [n];
	int** _map_copy = new int* [n];

	for (int i = 0; i < n; i++) {
		_map[i] = new int[m];
		_map_copy[i] = new int[m];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> _map[i][j];

			if (_map[i][j] == 0) {
				_map_v.push_back({i, j});
			}
		}
	}

	sort(_map_v.begin(), _map_v.end());

	do {
		while (!q.empty()) {
			q.pop();
		}

		for (int i = 0; i < n; i++) {
			memcpy(_map_copy[i], _map[i], sizeof(int) * m);
		}
        
		for (int i = 0; i < 3; i++) {
			_map_copy[_map_v.at(i).first][_map_v.at(i).second] = 1;
		}
        
	    for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (_map_copy[i][j] == 2) {
					q.push({ i, j });
				}
			}
		}

		func_14502_virusInfect(n, m, _map_copy, q);

		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (_map_copy[i][j] == 0) {
					cnt++;
				}
			}
		}
		
		if (cnt > max_safeZone) {
			max_safeZone = cnt;
		}

		reverse(_map_v.begin() + 3, _map_v.end());
	} while (next_permutation(_map_v.begin(), _map_v.end()));

	cout << max_safeZone << "\n";
    
    return 0;
}

결과

문제

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

접근 방식

• 1~n 까지 오름차순으로 정렬된 num_vector, stack_vector, 원하는 수열을 입력 받을 target_vector 를선언한다.
• target_v의 각 요소들에서 num의 top(back)과 값을 비교한다.
• 같으면 다음 target으로 이동하고 다르면 하나씩 뽑아서 비교하면서 stack에 넣는다.
• 넣는 중에 찾을 경우 다음 target으로 이동한다.
• 다 넣고 못찾았을 경우 stack을 확인한다.
• stack에서 하나씩 빼면서 탐색한다.
• stack이 비었는데 target이 남아있거나 , 원하는 값을 찾을 수 없는 경우 No로 판단한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, tmp, num_cur, flag;
    cin >> n;

    vector<int> num_v, stack_v, target_v;
    vector<char> res_v;

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        target_v.push_back(tmp);
        num_v.push_back(i + 1);
    }

    reverse(num_v.begin(), num_v.end());
    
    for (auto tmp_target : target_v) {
        flag = 0;

        if (num_v.size() == 0 && stack_v.size() == 0) {
            res_v.clear();
            break;
        }

        if (!stack_v.empty()) {
            if (tmp_target == stack_v.back()) {
                stack_v.pop_back();
                res_v.push_back('-');
                flag = 1;
                continue;
            }
        }

        while (true) {
            if (!num_v.empty()) {
                num_cur = num_v.back();
                stack_v.push_back(num_cur);
                res_v.push_back('+');
                num_v.pop_back();

                if (tmp_target == num_cur) {
                    stack_v.pop_back();
                    res_v.push_back('-');
                    flag = 1;
                    break;
                }
            }
            else {
                if (stack_v.empty())
                    break;

                while (!stack_v.empty()) {
                    if (tmp_target == stack_v.back()) {
                        stack_v.pop_back();
                        res_v.push_back('-');
                        flag = 1;
                        break;
                    }
                    else {
                        stack_v.pop_back();
                    }
                }
                
                if (!flag) {
                    res_v.clear();
                    break;
                }
            }
        }
    }


    if (res_v.empty()) {
        cout << "NO\n";
    }
    else {
        for (auto tmp_res : res_v) {
            cout << tmp_res << "\n";
        }
    }
    
    return 0;
}

결과

문제

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

접근 방식

• BFS로 영역나누기, 8방향 검사

코드

#include <iostream>
#include <utility> 
#include <queue> 
#include <cstring>

using namespace std;

int main() {
    int w = 1, h = 1;
    queue<pair<int, int>> q;
    int direc[8][2] = { {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1} };
    int visit_value, _x, _y;
    pair<int, int> front;

    while (true) {
        cin >> w >> h;

        if (w + h == 0){
            break;
        }

        int** _map = new int* [h];
        int** visit = new int* [h];
        for (int i = 0; i < h; i++) {
            _map[i] = new int[w];
            visit[i] = new int[w];
            memset(visit[i], 0, sizeof(int) * w);
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> _map[i][j];
            }
        }

        visit_value = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (visit[i][j] == 0 && _map[i][j] == 1) {
                    q.push({ i, j });
                    visit[i][j] = ++visit_value;
                }

                while (!q.empty()) {
                    front = q.front();
                    q.pop();

                    for (int i = 0; i < 8; i++) {
                        _x = front.first + direc[i][0];
                        _y = front.second + direc[i][1];

                        if (_x >= h || _x < 0) {
                            continue;
                        }

                        if (_y >= w || _y < 0) {
                            continue;
                        }

                        if (visit[_x][_y] != 0) {
                            continue;
                        }

                        if (_map[_x][_y] != 1) {
                            continue;
                        }

                        visit[_x][_y] = visit_value;
                        q.push({ _x, _y });
                    }
                }
            }
        }

        cout << visit_value << "\n";

        while (!q.empty()) {
            q.pop();
        }

        for (int i = 0; i < h; i++) {
            delete(_map[i]);
            delete(visit[i]);
        }
    }
    
    return 0;
}

결과

문제

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

접근 방식

• 정렬 후 이진탐색 구현 매개변수로 정렬된 벡터 전달 -> 10% 시간 초과
• 입출력 속도 개선 -> 10% 시간 초과
• 정렬된 벡터를 전역 변수로 접근(매개변수로 전달하는 과정에서 시간이 많이 걸릴 수 있다고 함) -> 통과

코드

#include <iostream>
#include <vector>
#include <algorithm> 
#include <cmath> 

using namespace std;

vector<int> func_1920_An;

int func_1920_isExist(int find_value) {
    int res = 0;
    int start_index = 0, end_index = func_1920_An.size();
    int index = (int)floor((start_index + end_index) / 2);

    while(start_index < end_index) {
        if (find_value == func_1920_An.at(index)) {
            res = 1;
            break;
        }

        if (start_index == index){
            break;
        }

        if (find_value > func_1920_An.at(index)) {
            start_index = index;
        }

        if (find_value < func_1920_An.at(index)) {
            end_index = index;
        }

        index = (int)floor((start_index + end_index) / 2);
    }

    return res;
}


int main() {
    int n, m, tmp;
    vector<int> Am;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        func_1920_An.push_back(tmp);
    }

    sort(func_1920_An.begin(), func_1920_An.end());

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        Am.push_back(tmp);
    }

    for (auto m_tmp : Am) {
        cout << func_1920_isExist(m_tmp) << "\n";
    }
    
    return 0;
}

결과

문제

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

접근 방식

• 다이나믹 프로그래밍 분류에 있는 문제이므로 점화식을 찾아 DP로 구현

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

위 규칙을 기반으로 점화식을 찾아보자.

가능한 연산과 규칙을 나열해보면 최종적으로 dp[n] = 1 + min(dp[n-1], dp[n/2], dp[n/3]) 이라는 점화식을 찾을 수 있다. 점화식의 의미는 현재 수에 대한 연산 횟수 증가(1) + 가능한 이전 연산 중 최소 값 ( min(...) ) 이다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    int min, num;

    cin >> num;

    int* dp = new int[num+2];
    memset(dp, 0, sizeof(int) * (num+2));
    
    for (int i = 2; i <= num; i++) {
        dp[i]++;
        min = 0;

        if (min > dp[i - 1] || min == 0)
            min = dp[i - 1];

        if (i % 2 == 0) {
            if (min > dp[i / 2])
                min = dp[i / 2];
        }

        if (i % 3 == 0) {
            if (min > dp[i / 3])
                min = dp[i / 3];
        }

        dp[i] += min;
    }

    cout << dp[num] << "\n";
    
    return 0;
}

결과

​

문제

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

접근 방식

• 기본 Map과 색약 Map을 만들어 BFS로 구역을 나눠줌
• 틀렸습니다. 코드와 정답 코드 차이

// 틀린 코드
if (map_visit[i][j] == 0) {
	q.push({i, j});
    visit_value++;
}

// 정답 코드
if (map_visit[i][j] == 0) {
	q.push({i, j});
	map_visit[i][j] = ++visit_value;
}

코드

#include <iostream>
#include <cstring>
#include <utility> 
#include <queue> 

using namespace std;

void func_10026_bfs(queue<pair<int, int>> q, char **_map, int **visited, int visit_value, int n) {
    pair<int, int> tmp_coord;
    int _x, _y;
    char tmp_color;
    int direct[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

    while (!q.empty()) {
        tmp_coord = q.front();
        tmp_color = _map[tmp_coord.first][tmp_coord.second];
        q.pop();

        for (int i = 0; i < 4; i++) {
            _x = tmp_coord.first + direct[i][0];
            _y = tmp_coord.second + direct[i][1];

            if (_x >= n || _x < 0)
                continue;
            
            if (_y >= n || _y < 0)
                continue;

            if (visited[_x][_y] != 0)
                continue;

            if (_map[_x][_y] != tmp_color)
                continue;

            visited[_x][_y] = visit_value;
            q.push({_x, _y});
        }
    }
}

int main() {
    queue<pair<int, int>> q;
    int visit_value, map_max, map_rg_max;
    
    int n;
    cin >> n;

    char** map_origin = new char* [n];
    char** map_rg = new char* [n];
    int** map_visit = new int* [n];
    int** map_rg_visit = new int* [n];

    for (int i = 0; i < n; i++) {
        map_origin[i] = new char[n];
        map_rg[i] = new char[n];
        map_visit[i] = new int[n];
        map_rg_visit[i] = new int[n];

        memset(map_visit[i], 0, sizeof(int) * n);
        memset(map_rg_visit[i], 0, sizeof(int) * n);
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++) {
            cin >> map_origin[i][j];
            
            if (map_origin[i][j] == 'R')
                map_rg[i][j] = 'G';
            else
                map_rg[i][j] = map_origin[i][j];
        }
    }

    visit_value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_visit[i][j] == 0) {
                q.push({i, j});
                map_visit[i][j] = ++visit_value;
            }

            func_10026_bfs(q, map_origin, map_visit, visit_value, n);
        }
    }


    while (!q.empty()) {
        q.pop();
    }

    visit_value = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_rg_visit[i][j] == 0) {
                q.push({ i, j });
                map_rg_visit[i][j] = ++visit_value;
            }

            func_10026_bfs(q, map_rg, map_rg_visit, visit_value, n);
        }
    }

    map_max = 0;
    map_rg_max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_max < map_visit[i][j]) {
                map_max = map_visit[i][j];
            }

            if (map_rg_max < map_rg_visit[i][j]) {
                map_rg_max = map_rg_visit[i][j];
            }
        }
    }
    
    cout << map_max << " " << map_rg_max << "\n";
    
    return 0;
}

결과

1. 문제

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

2. 접근 방식

• Stack 활용

3. 코드

#include <iostream>
#include <stack> 

using namespace std;

int main() {
    int test_case, tmp, sum=0;
    cin >> test_case;

    stack<int> stack_zero;

    for (int i = 0; i < test_case; i++) {
        cin >> tmp;
        if (tmp==0) {
            stack_zero.pop();
        }
        else {
            stack_zero.push(tmp);
        }
    }
    
    while (!stack_zero.empty()) {
        sum += stack_zero.top();
        stack_zero.pop();
    }

    cout << sum << "\n";
    
    return 0;
}

4. 결과

1. 문제

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

2. 접근 방식

• 1차 : 문제에서 알려준 공식대로 구현 -> 50점, 작은 문자열에서는 잘 동작하지만 큰 문자열에서는 시간초과
• 2차 :  합동식 활용 A * B mod C -> (A mod C) * (B mod C) -> 통과

3. 코드

• 1차 코드

#include<iostream>
#include <cmath> 

typedef unsigned long long ll;

using namespace std;

int main() {
    int str_len;
    cin >> str_len;
    string str;
    cin >> str;

    int a, r = 31, M = 1234567891;
    ll sum = 0;

    for (int i = 0; i < str_len; i++) {
        a = (str[i] - 'a') + 1;
        sum += a * pow(r, i);
    }

    cout << sum % M << "\n";
}

• 2차 코드

#include<iostream>

using namespace std;

typedef unsigned long long ll;

int main() {
    int str_len;
    cin >> str_len;

    string str;
    cin >> str;

    ll r, sum = 0, a;
    int M = 1234567891;

    for (int i = 0; i < str_len; i++) {
        a = (str[i] - 'a') + 1;

        r = 1;
        for (int j = 0; j < i; j++) {
            r *= 31;
            r %= M;
        }

        sum += a * r;
        sum %= M;
    }
    
    cout << sum;
}

4. 결과

1. 문제

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

2. 접근 방식

• 1차 : 전체 블록의 평균(높이)을 구해서 해당 높이까지 블록을 맞춰주는 로직 작성 -> 틀림
• 2차 : 0~가장 큰 높이의 블록을 기준으로 각 케이스를 계산하여 가장 시간이 빠른 경우 선택 -> 1%에서 틀림
• 3차 : 위와 동일하지만 블록을 먼저 다 회수하고 설치 진행 -> 시간초과
• 4차 : 제거할 블록과 쌓을 블록의 개수를 구하고 시간을 나중에 구함 -> 통과

3. 반례

// 1 64
3 4 1
64 64 64 64
64 64 64 64
64 64 64 63

// 22 63
3 4 0
64 64 64 64
64 64 64 64
64 64 64 63

// 2 0
3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

// 2 1
1 3 68
0 0 1

// 250 35
3 4 11
29 51 54 44
22 44 32 62
25 38 16 2

// 355 32 
4 4 36
15 43 61 21
19 33 31 55
48 63 1 30
31 28 3 8

// 0 0
1 1 0
0

// 768 128
2 2 0
256 256
0 0

// 879 10
7 7 6000
30 21 48 55 1 1 4
0 0 0 0 0 0 0
15 4 4 4 4 4 8
20 40 60 10 20 30 2
1 1 1 1 1 1 9
24 12 33 7 14 25 3
3 3 3 3 3 3 32

// 350 40
2 2 35
20 10
190 40

// 290 170
2 2 68
120 90
250 170

4. 코드

• 1차 코드 : 동일한 시간일 경우 높은 높이 조건을 충족하지 못함. ( + 틀린 케이스 존재)

#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int n, m, inventory, height, time = 0;
    double sum = 0;

    cin >> n >> m >> inventory;

    // 맵 입력
    int** map = new int*[n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            sum += map[i][j];
        }
    }

    // 전체 높이 결정 (인벤토리 기준)
    if (inventory > 0) {
        height = round(sum / (n * m));
    }
    else {
        height = floor(sum / (n * m));
    }
    
    // 땅 다듬기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == height)
                continue;

            if (map[i][j] > height) {
                time += 2;
                map[i][j] -= 1;
                inventory++;
            }
            else {
                time += 1;
                map[i][j] += 1;
                inventory--;
            }

        }
    }

    cout << time << " " << height << "\n";
    
    return 0;
}

• 2차 코드 : 틀린 케이스 존재 (앞에부터 가져와서 쌓기 때문에 블록이 부족한 경우 발생)

#include<iostream>
#include<cmath>

using namespace std;

// 현재 맵에서 입력된 높이까지 얼마의 시간이 걸리는지 반환
int func_18111_getTime(int height, int n, int m, int inventory, int **map) {
    int time = 0, tmp_map;
    bool flag = true;

    // map 전체 스캔
    for (int i = 0; i < n && flag; i++) {
        for (int j = 0; j < m && flag; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;
			
            // 현재 블록의 높이가 원하는 높이보다 높으면 블록 회수
            if (tmp_map > height) {
                while (tmp_map != height) {
                    time += 2;
                    tmp_map -= 1;
                    inventory++;
                }
            }
            else {
                // 블록 설치 (인벤토리가 부족하면 flag == false
                while (tmp_map != height) {
                    if (inventory > 0) { 
                        inventory--; 
                    }
                    else {
                        flag = false;
                    }

                    if (!flag) 
                        break;

                    time += 1;
                    tmp_map += 1;
                }

                if (!flag || tmp_map != height) {
                    flag = false;
                    break;
                }
            }

        }
    }
    
    // flag 가 false 면 time 초기화
    if (!flag) {
        time = 0;
    }

    return time;
}

int main() {
    int n, m, inventory, height=-1, time = 0, tmp, min = 2100000000, max=0;
    double sum = 0;

    cin >> n >> m >> inventory;

	// 맵 정보 입력 및 블록 최대값 구하기
    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (max < map[i][j]) {
                max = map[i][j];
            }
        }
    }
    
    // 0 ~ 블록 최대 값 중 시간이 가장 빠르고, 높이가 높은 값 찾기
    for (int i = 0; i <= max; i++) {
        tmp = func_18111_getTime(i, n, m, inventory, map);

        if (min >= tmp && tmp > 0) {
            if (min == tmp && height > i) continue;
            min = tmp;
            height = i;
        }
    }

    // 찾을 수 없으면 0으로 초기화
    if (min == 2100000000 || height == -1) {
        min = 0;
        height = 0;
    }
    
    cout << min << " " << height << "\n";
    
    return 0;
}

• 3차 코드 : 입력 높이(height)보다 높은 블록들 먼저 회수하고, 낮은 블록 쌓기

#include<iostream>
#include<cmath>

using namespace std;

int func_18111_getTime(int height, int n, int m, int inventory, int **map) {
    int time = 0, tmp_map;
    bool flag = true;

    // 블록 회수 (높이 낮추기)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;
            
            if (tmp_map > height) {
                while (tmp_map != height) {
                    time += 2;
                    tmp_map -= 1;
                    inventory++;
                }
            }
        }
    }
    
    // 블록 설치 (부족하면 flag == false)
    for (int i = 0; i < n && flag; i++) {
        for (int j = 0; j < m && flag; j++) {
            tmp_map = map[i][j];

            if (tmp_map == height)
                continue;

            if (tmp_map < height) {
                while (tmp_map != height) {
                    if (inventory > 0) {
                        inventory--;
                    }
                    else {
                        flag = false;
                    }

                    if (!flag)
                        break;

                    time += 1;
                    tmp_map += 1;
                }

                if (!flag || tmp_map != height) {
                    flag = false;
                    break;
                }
            }
        }
    }

    if (!flag) {
        time = 0;
    }

    return time;
}

int main() {
    int n, m, inventory, height=-1, time = 0, tmp, min = 2100000000, max=0;
    double sum = 0;

    cin >> n >> m >> inventory;

    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (max < map[i][j]) {
                max = map[i][j];
            }
        }
    }
    
    for (int i = 0; i <= max; i++) {
        tmp = func_18111_getTime(i, n, m, inventory, map);

        if (min >= tmp && tmp > 0) {
            if (min == tmp && height > i) continue;
            min = tmp;
            height = i;
        }
    }

    if (min == 2100000000 || height == -1) {
        min = 0;
        height = 0;
    }
    
    cout << min << " " << height << "\n";
    
    return 0;
}

• 4차 코드 : 통과

#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int n, m, inventory, min = 2100000000, max = 0;
    int height = -1, time = 0, tmp_block, time_min= 2100000000;
    double sum = 0;

    cin >> n >> m >> inventory;

    // 맵 입력
    int** map = new int* [n];
    for (int i = 0; i < n; i++) {
        map[i] = new int[m];
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];

            if (max < map[i][j]) {
                max = map[i][j];
            }

            if (min > map[i][j]) {
                min = map[i][j];
            }
        }
    }

    int build_block, remove_block;

    // 맵의 최소 블록 높이부터 가장 높은 블록까지 반복
    for (int h = min; h <= max; h++) {
        build_block = 0;
        remove_block = 0;

        // h에서의 회수할 블록, 설치할 블록 개수 구하기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tmp_block = map[i][j];

                // 현재 블록이 h보다 낮으면 설치할 블록 개수 누적
                if (h > tmp_block) {
                    build_block += h - tmp_block;
                }

                // 현재 블록이 h 보다 높으면 회수할 블록 개수 누적
                if (h < tmp_block) {
                    remove_block += tmp_block - h;
                }
            }
        }

        // 설치할 블록 개수가 인벤토리와 회수한 블록의합보다 부족한지 검사
        if (build_block <= remove_block + inventory) {
            time = remove_block * 2 + build_block;

            if (time_min >= time) {
                if (height > h) continue;
                time_min = time;
                height = h;
            }
        }
    }

    cout << time_min << " " << height << "\n";
    
    return 0;
}

5. 결과

1. 문제

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

2. 접근 방식

• mod연산의 성질을 통해 큰 제곱수를 연산하지 않고 mod 값을 알아냄
• 빠른 모듈로 거듭제곱법을 적용함

3. 코드

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ll;

int func_1009_mod(int a, int b) {
    vector<int> tmp, tmp2;
    int *x;
    ll res = 1;

    while(b!=0) {
        tmp.push_back(b % 2);
        b /= 2;
    }

    x = new int[21];
    x[0] = a % 10;
    for (int j = 1; j <= 20; j++) {
        x[j] = (x[j-1] * x[j - 1]) % 10;
    }

    for (int i = 0; i < tmp.size(); i++) {
        if (tmp.at(i) == 1) {
            res *= x[i];
        }
    }

    if (res % 10 == 0) res = 10;
    else res %= 10;
    
    return res;
}

int main() {
    int n, a, b;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        cout << func_1009_mod(a, b) << "\n";
    }
    
    return 0;
}

4. 결과

• C++로 구현시 큰 수를 변수 하나로 처리하기 어려워 다른 방법을 찾아야했지만, 파이썬을 활용하면 Pow 연산만으로 결과를 구할 수 있음
• 파이썬 활용하면 좋은 문제인듯함

1. URL : https://www.acmicpc.net/workbook/view/1152

2. 문제풀이

• 구슬 탈출2 (골드1)
• 2048(Easy) (골드2)
• 뱀 (골드 5)
• 시험 감독(브론즈 2)

#include <iostream>
#include <vector>
#include <cmath> 

using namespace std;

int main() {
	double n, tmp, b, c, sum=0;
	double sub_supervisor;

	cin >> n;
	vector<double> exam_room;

	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		exam_room.push_back(tmp);
	}

	cin >> b >> c;

	for (auto exam : exam_room) {
        if (exam - b <= 0) continue;
		sum += ceil((exam - b) / c);
	}

	printf("%0.lf\n", sum + n);
    
    return 0;
}

• 주사위 굴리기 (골드 4)

문제 1. 동전 0

• 가장 금액이 큰 동전부터 개수를 세면서 k원에서 차감해줌
• k가 0이되면 동전의 개수를 출력 

#include <iostream>
#include <map> 

using namespace std;

int main() {
	int n, k, tmp;
	map<int, int> m;
	map<int, int>::reverse_iterator reiter;

	cin >> n >> k;
	
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		m[tmp] = 0;
	}

	for(reiter = m.rbegin(); reiter != m.rend(); reiter++) {
		while (reiter->first <= k) {
			m[reiter->first]++;
			k -= reiter->first;
		}

		if (k <= 0) break;
	}

	tmp = 0;
	for (reiter = m.rbegin(); reiter != m.rend(); reiter++) {
		if (reiter->second > 0) {
			tmp += reiter->second;
		}
	}

	cout << tmp << "\n";
    
    return 0;
}

문제 2. 회의실 배정

문제 3. ATM

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

int main() {
	int test_case;
	int a, sum=0;
	
	vector<int> v;

	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		cin >> a;
		v.push_back(a);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < test_case; i++) {
		for (int j = 0; j <= i; j++) {
			sum += v[j];
		}
	}

	cout << sum << "\n";
    
    return 0;
}

문제 4. 잃어버린 괄호

문제 5. 주유소

결과

문제 1. 피보나치 함수

• 피보나치 f(n) 이 몇개의 f(0)과 f(1)로 이루어 져 있는지 출력하는 문제
• 점화식(?) { f(i).first, f(i).second } = { f(i-1).first+f(i-2).first, f(i-1).second+f(i-2).second } 을 찾음

#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int main() {
	int test_case;
	cin >> test_case;
	
	vector<pair<int, int>> f;

	f.push_back({ 1, 0 });
	f.push_back({ 0, 1 });

	for (int i = 2; i <= 40; i++) {
		f.push_back({f.at(i-1).first + f.at(i-2).first, f.at(i-1).second + f.at(i-2).second});
	}

	int* n = new int[test_case];
	for (int i = 0; i < test_case; i++) {
		cin >> n[i];
		cout << f.at(n[i]).first << " " << f.at(n[i]).second << "\n";
	}
    
    return 0;
}

문제 2. 신나는 함수 실행

문제 3. 01타일

문제 4. 파도반 수열

문제 5. RGB 거리

문제 6. 정수 삼각형

문제 7. 계단 오르기

문제 8. 1로 만들기

문제 9. 쉬운 계단 수

문제 10. 포도주 시식

문제 11. 가장 긴 증가하는 부분 수열

문제 12. 가장 긴 바이토닉 부분 수열

문제 13. 전깃줄

문제 14. LCS

문제 15. 연속합

문제 16. 평범한 배낭

결과

문제 1. DFS와 BFS

#include <iostream>
#include <vector>
#include <algorithm> 
#include <cstring> 
#include <queue> 

using namespace std;

void func_1260_dfs_recursion(int n, vector<int> * graph, bool* visited) {
	visited[n] = true;
	cout << n << " ";

	for (auto node : graph[n]) {
		if (!visited[node]) {
			func_1260_dfs_recursion(node, graph, visited);
		}
	}
}

void func_1260_bfs_queue(int n, vector<int> * graph, bool* visited) {
	queue<int> q;
	int now_node;

	visited[n] = true;
	q.push(n);

	while (!q.empty()) {
		now_node = q.front();
		q.pop();
		cout << now_node << " ";

		for (auto node : graph[now_node]) {
			if (!visited[node]) {
				visited[node] = true;
				q.push(node);
			}
		}
	}
	cout << "\n";
}

int main() {
	int n, m, start_node, u, v;
	
	cin >> n >> m >> start_node;

	vector<int> *graph = new vector<int>[n+1];

	bool *visited = new bool[n+1];
	memset(visited, 0, sizeof(bool) * (n+1));

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
    
	func_1260_dfs_recursion(start_node, graph, visited);
	cout << "\n";

	memset(visited, 0, sizeof(bool) * (n + 1));
	func_1260_bfs_queue(start_node, graph, visited);
    
	return 0;
}

문제 2. 바이러스

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> 

using namespace std;

static int func_2606_cnt;

void func_2606_dfs(int start, vector<int> *graph, bool* visited) {
	visited[start] = true;

	func_2606_cnt++;

	for (auto node : graph[start]) {
		if (!visited[node]) {
			func_2606_dfs(node, graph, visited);
		}
	}
}

int main() {
	int n, m, u, v;

	cin >> n >> m;

	vector<int> *graph = new vector<int>[n+1];

	bool* visited = new bool[n+1];
	memset(visited, 0, sizeof(bool) * (n+1));

	func_2606_cnt = 0;

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
    
	func_2606_dfs(1, graph, visited);

	cout << func_2606_cnt -1 << "\n";
    
	return 0;
}

문제 3. 단지 번호 붙이기

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<utility> 

using namespace std;

int func_2667_bfs(int cnt, int n, queue<pair<int, int>> q, int **map, int ** v) {
	int _x, _y, a=0;
	pair<int, int> now, tmp;

	int** direc = new int* [4];
	for (int i = 0; i < 4; i++) {
		direc[i] = new int[2];
		if (i == 0) {
			_x = 0;
			_y = -1;
		}
		else if (i == 1) {
			_x = 1;
			_y = 0;
		}
		else if (i == 2) {
			_x = 0;
			_y = 1;
		}
		else if (i == 3) {
			_x = -1;
			_y = 0;
		}
		direc[i][0] = _x;
		direc[i][1] = _y;
	}

	while (!q.empty()) { 
		now = q.front();
		q.pop();
		if (v[now.first][now.second] != 1) {
			v[now.first][now.second] = 1;
			a++;
		}

		for (int i = 0; i < 4; i++) {
			_x = now.first + direc[i][0];
			_y = now.second + direc[i][1];

			if (_x < 0 || _x >= n) {
				continue;
			}
			if (_y < 0 || _y >= n) {
				continue;
			}
			
			if (map[_x][_y] == 0) {
				continue;
			}

			if (v[_x][_y] == 1) {
				continue;
			}

			// 방문한적 없는 좌표인데 값이 1보다 크면 현재 카운트로 덮어쓰기 및 방문처리
			if (map[_x][_y] >= 1) {
				v[_x][_y] = 1;
				map[_x][_y] = cnt;
				q.push({_x, _y});
				//cout << _x << ", " << _y << "\n";
				a++;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		delete direc[i];
	}

	return a;
}

int main() {
	int n, cnt =0;
	string str;
	queue<pair<int, int>> q;
	vector<int> m;
	int tmp_m;

	cin >> n;

	int** v = new int* [n];
	for (int i = 0; i < n; i++) {
		v[i] = new int[n];
		for (int j = 0; j < n; j++) {
			v[i][j] = 0;
		}
	}

	int** _map = new int* [n];
	for (int i = 0; i < n; i++) {
		str = "";
		_map[i] = new int[n];

		cin >> str;
		for (int j = 0; j < n; j++) {
			_map[i][j] = str[j] - '0';
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (_map[i][j] == 1) {
				q.push({ i, j });
				
				tmp_m = func_2667_bfs(cnt+1, n, q, _map, v);
				if (tmp_m != 0) {
					m.push_back(tmp_m);
					cnt++;
				}
			}
			
		}
	}

	sort(m.begin(), m.end());

	cout << cnt << "\n";
	for (int i = 0; i < cnt; i++) {  
		cout << m[i] << "\n";
	}
    return 0;
}

문제 4. 유기농 배추

#include <iostream>
#include <utility>
#include <cstring>
#include <queue> 

using namespace std;

int main() {
	int test_case;
	int n, m, k;
	int u, v;
	int _x, _y;
	pair<int, int> dir[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // 상, 우, 하, 좌
	pair<int, int> tmp_q;
	int graph_count = 0;

	int** _map;
	int** _visit;
	queue<pair<int, int>> q;


	cin >> test_case;
	for (int a = 0; a < test_case; a++) {
		cin >> m >> n >> k;

		// Map 생성 및 초기화
		_map = new int* [n];
		_visit = new int* [n];

		for (int i = 0; i < n; i++) {
			_map[i] = new int[m];
			_visit[i] = new int[m];

			memset(_map[i], 0, sizeof(int) * m);
			memset(_visit[i], 0, sizeof(int) * m);

		}

		// Map 업데이트
		for (int i = 0; i < k; i++) {
			cin >> u >> v;
			_map[v][u] = 1;
		}

		graph_count = 0;


		// Map 탐색
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				// 지도에서 현재 좌표가 1이고 방문한 적이 없으면 현재 좌표를 q에 등록하고 방문 처리
				if (_map[i][j] == 1 && _visit[i][j] != 1) {
					q.push({i, j});
					_visit[i][j] = 1;
					
					graph_count++;
				}

				// q에 값이 있으면
				while (!q.empty()) {
					tmp_q = q.front();
					q.pop();
					
					// 현재 좌표에서 인접한 4방향 좌표를 검사, 위부터 시계방향
					for (int i = 0; i < 4; i++) {
						_x = tmp_q.first + dir[i].first;
						_y = tmp_q.second + dir[i].second;

						// 경계선 검사
						if (_x >= n || _x < 0)
							continue;

						if (_y >= m || _y < 0) 
							continue;

						// 값 검사
						if (_map[_x][_y] == 0)
							continue;
						
						// 방문여부 검사
						if (_visit[_x][_y] == 1)
							continue;

						// 방문기록 남기고 다음 작업대상에 추가
						_visit[_x][_y] = 1;
						q.push({_x, _y});
					}
				}
			}
		}

		cout << graph_count << "\n";

		// 메모리 해제
		for (int i = 0; i < n; i++) {
			free(_map[i]);
			free(_visit[i]);
		}
	}
    
    return 0;
}

문제 5. 미로 탐색

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

// 노드 정보 저장용 클래스
class func_2178_node {
public:
	int x;
	int y;
	int value;
	int visited;
};

int func_2178_BFS(int n, int m, func_2178_node **_map, int *start_node, int *end_node) {
	// BFS 탐색을 위한 큐 생성 현재 노드 저장
	queue<func_2178_node> q;
	func_2178_node tmp_node, now_node;

	// 상0, 우1, 하2, 좌3 
	int** direction = new int*[4];
	for (int i = 0; i < 4; i++) {
		direction[i] = new int[2];

		if (i == 0) {
			direction[i][0] = 0;
			direction[i][1] = -1;
		}
		if (i == 1) {
			direction[i][0] = 1;
			direction[i][1] = 0;
		}
		if (i == 2) {
			direction[i][0] = 0;
			direction[i][1] = 1;
		}
		if (i == 3) {
			direction[i][0] = -1;
			direction[i][1] = 0;
		}
	}


	// 시작노드의 방문 여부 변경
	_map[start_node[0]][start_node[1]].visited = 1;
	// 시작노드 넣기
	q.push(_map[start_node[0]][start_node[1]]);

	// 큐에 값이 있으면 탐색 시작
	while (!q.empty()) {
		// 현재 큐의 값 가져오기 + pop
		now_node = q.front();
		q.pop();

		// 인접 노드 탐색 (시계방향으로 탐색)
		for (int i = 0; i < 4; i++) {
			// 현재 좌표가 좌우를 넘어가는지 확인
			if (now_node.x + direction[i][0] <= 0 || now_node.x + direction[i][0] > n) {
				continue;
			}

			// 현재 좌표가 상하를 넘어가는지 확인
			if (now_node.y + direction[i][1] <= 0 || now_node.y + direction[i][1] > m) {
				continue;
			}

			// 이동한 값이 맵 안에 있으면 노드 이동
			tmp_node = _map[now_node.x + direction[i][0]][now_node.y + direction[i][1]];

			// 값이 1이 아닌지 검사, 아니면 continue;
			if (tmp_node.value == 0) {
				continue;
			}

			// 방문 여부가 없는지 검사 (방문했으면 다음거)
			if (tmp_node.visited) {
				continue;
			}

			_map[tmp_node.x][tmp_node.y].visited = _map[now_node.x][now_node.y].visited + 1;
			q.push(_map[tmp_node.x][tmp_node.y]);
		}
	}

	return _map[n][m].visited;
}

int main() {
	int n, m;
	int* start_node = new int[2];
	int* end_node = new int[2];
	string str_input;

	cin >> n >> m;

	start_node[0] = 1;
	start_node[1] = 1;
	end_node[0] = n;
	end_node[1] = m;

	func_2178_node** map = new func_2178_node*[n+1];
	for (int i = 1; i <= n; i++) {
		map[i] = new func_2178_node[m+1];
	}

	for (int i = 1; i <= n; i++) {
		cin >> str_input;
		for (int j = 1; j <= m; j++) {
			map[i][j].x = i;
			map[i][j].y = j;
			map[i][j].value = str_input[j-1] - '0';
			map[i][j].visited = 0;
		}
	}

	cout << func_2178_BFS(n, m, map, start_node, end_node) << "\n";

    return 0;
}

문제 6. 토마토

#include <iostream>
#include <queue> 

using namespace std;

class func_7576_tomato {
public:
	int x;
	int y;
	int visited;
	int value;
};

void func_7576_bfs(int n, int m, func_7576_tomato** box, queue<func_7576_tomato> q) {
	func_7576_tomato now_tomato, tmp_tomato;

	// 방향 정의 (시계방향)
	int** direc = new int*[4];
	int _x, _y;
	for (int i = 0; i < 4; i++) {
		direc[i] = new int[2];

		// 상
		if (i == 0) {
			_x = 0;
			_y = -1;
		}
		// 우
		if (i == 1) {
			_x = 1;
			_y = 0;
		}
		// 하
		if (i == 2) {
			_x = 0;
			_y = 1;
		}
		// 좌
		if (i == 3) {
			_x = -1;
			_y = 0;
		}

		direc[i][0] = _x;
		direc[i][1] = _y;
	}

	// bfs 탐색 시작 
	while (!q.empty	()) {
		now_tomato = q.front();
		q.pop();

		// 각 방향별 탐색
		for (int i = 0; i < 4; i++) {
			// 이동한 범위가 토마토 상자 내부인지 검사 (x축)
			if (now_tomato.x + direc[i][0] < 0 || now_tomato.x + direc[i][0] >= n) {
				continue;
			}
			// 이동한 범위가 토마토 상자 내부인지 검사 (y축)
			if (now_tomato.y + direc[i][1] < 0 || now_tomato.y + direc[i][1] >= m) {
				continue;
			}

			tmp_tomato = box[now_tomato.x + direc[i][0]][now_tomato.y + direc[i][1]];

			// 해당 위치가 벽인지 검사
			if (tmp_tomato.value != 0) {
				continue;
			}

			// 해당 위치에 숙성되지 않은 토마토가 있으면 숙성 시키고 몇 일차에 숙성시켰는지 입력 후 큐에 등록
			box[tmp_tomato.x][tmp_tomato.y].value = 1;
			box[tmp_tomato.x][tmp_tomato.y].visited = now_tomato.visited + 1;
			q.push(box[tmp_tomato.x][tmp_tomato.y]);
		}
	}
}

int main() {
	int m, n, tmp, max;
	queue<func_7576_tomato> q;

	// 노드 개수
	cin >> m >> n;

	// 노드 생성
	func_7576_tomato** box = new func_7576_tomato*[n];
	for (int i = 0; i < n; i++) {
		box[i] = new func_7576_tomato[m];
	}

	// 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			box[i][j].x = i;
			box[i][j].y = j;
			box[i][j].visited = 0;
			box[i][j].value = 0;
		}
	}

	// 입력값 받기, 입력에 따른 값 설정
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tmp;
			box[i][j].value = tmp;
			
			//입력 값이 1이면 큐에 등록
			if (tmp == 1) {
				q.push(box[i][j]);
			}
		}
	}

	func_7576_bfs(n, m, box, q);

	max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 숙성안된 토마토가 있으면 -1
			if (box[i][j].value == 0) {
				max = -1;
				break;
			}
			// 최대값 찾아서 갱신
			if (max < box[i][j].visited) {
				max = box[i][j].visited;
			}
		}
		if (max == -1) {
			break;
		}
	}

	cout << max << "\n";
    
	return 0;
}

문제 7. 토마토

문제 8. 숨바꼭질

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

void func_1697_bfs(int k, queue<int> q, int *visited) {
    int now;
    while (!q.empty()) {
        now = q.front();
        q.pop(); 

        if (now == k) {
            break;
        }

        if (visited[now - 1] == 0 && (now - 1) >= 0) {
            visited[now - 1] = visited[now] + 1;
            q.push(now-1);
        }

        if ( (now+1) < 100000 && visited[now + 1] == 0) {
            visited[now + 1] = visited[now] + 1;
            q.push(now+1);
        }
        
        if ( (now * 2) <= 100000 && visited[now * 2] == 0) {
                visited[now * 2] = visited[now] + 1;
                q.push(now * 2);
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    
    int* visited = new int[100000];
    memset(visited, 0, sizeof(int) * 100000);
    queue<int> q;

    q.push(n);
    visited[n] = 1;
    func_1697_bfs(k, q, visited);

    cout << visited[k]-1 << "\n";
    
    return 0;
}

문제 9. 벽 부수고 이동하기

문제 10. 나이트의 이동

문제 11. 이분 그래프

결과

문제 1. 수 정렬하기 (브론즈 1)

• vector로 입력 받아 sort로 정렬

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int a, num;
	vector<int> v;
    
	cin >> a;
	
	for (int i = 0; i < a; i++) {
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v.at(i) << "\n";
	}
    
    return 0;
}

문제 2. 수 정렬하기 2 (실버 5)

• vector로 입력 받고 sort로 정렬 (1번과 동일)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int a, num;
	vector<int> v;
    
	cin >> a;
	
	for (int i = 0; i < a; i++) {
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v.at(i) << "\n";
	}
    
    return 0;
}

문제 3. 수 정렬하기 3 (실버 5)

• map에 입력 받은 수의 개수를 카운팅함

#include<iostream>
#include<map>

using namespace std;

int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    
	int a, num;
	map<int, int> m;
	map<int, int>::iterator iter;
	cin >> a;

	for (int i = 0; i < a; i++) {
		cin >> num;
		if (m[num] == 0) m[num] = 1;
		else m[num]++;
	}

	for (iter = m.begin(); iter != m.end(); iter++) {
		for (int i = 0; i < iter->second; i++) {
			cout << iter->first << "\n";
		}
	}
    return 0;
}

문제 4. 통계학 (실버 4)

• 문제 자체는 어렵지 않지만, 함정이 많은 문제였음
• 평균값이 -1과 0 사이에 존재할 경우 별도의 연산이 없으면 -0으로 출력되는 문제가 존재
• 최빈값(가장 많이 나온 값)을 구하고 여러개 일 경우 2번째로 작은 값을 구하는 부분 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<numeric>

using namespace std;

int main() {
	int a;
	double tmp, sum, aver, max, min_val, max_val;

	cin >> a;
	map<double, int> m;
	vector<double> v, v_mode;

	sum = 0;
	for (int i = 0; i < a; i++) {
		cin >> tmp;

		v.push_back(tmp);

		if (m[tmp] == 0) {
			m[tmp] = 1;
		}
		else {
			m[tmp]++;
		}

		sum += tmp;
	}

	aver = accumulate(v.begin(), v.end(), 0.0) / v.size();
	printf("%.0f\n", aver<=0&&aver>-1?(int)aver:aver);

	int cnt = 0;
	int index = (int) floor(a / 2);
	sort(v.begin(), v.end());
	cout << v.at(index) << "\n";

	max = 0;
	for (auto num : m) {
		if (num.second > max) {
			max = num.second;
		}
	}
    
	cnt = 0;
	for (auto num : m) {
		if (num.second == max) {
			v_mode.push_back(num.first);
		}
	}
	
	if (v_mode.size() > 1) {
		sort(v_mode.begin(), v_mode.end());
		cout << v_mode.at(1) << "\n";
	}
	else
	{
		cout << v_mode.at(0) << "\n";
	}

	min_val = v.at(0);
	max_val = v.at(v.size() - 1);
	cout << max_val - min_val << "\n";
    
	return 0;
}

문제 5. 소트인사이드 (실버 5)

• vector로 입력받고 오름차순 정렬 후 역으로 출력(내림차순 정렬)

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	vector<char> v;
	string str;
	cin >> str;

	for (int i = 0; i < str.length(); i++) {
		v.push_back(str[i]);
	}

	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	for (auto v_tmp : v) {
		cout << v_tmp;
	}
    
	return 0;
}

문제 6. 좌표 정렬하기 (실버 5)

• x좌표로 정렬 후 y좌표 기준 정렬

#include <iostream>
#include <vector>
#include <utility> 
#include <algorithm> 

using namespace std;

int main() {
	int a, b, test_case;
	vector<pair<int, int>> v; 

	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> a >> b;
		v.push_back({a, b});
	}

	sort(v.begin(), v.end());

	for (auto v_tmp : v) {
		cout << v_tmp.first << " "  << v_tmp.second << "\n";
	}
    
    return 0;
}

문제 7. 좌표 정렬하기 2 (실버 5)

• y좌표로 정렬 후 x좌표로 정렬
• 문제 6번의 코드에서 입력 받는 순서와 출력 받는 순서만 반대로 해줌

#include <iostream>
#include <vector>
#include <utility> 
#include <algorithm> 

using namespace std;

int main() {
	int a, b, test_case;
	vector<pair<int, int>> v; 

	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> a >> b;
		v.push_back({b, a});
	}

	sort(v.begin(), v.end());

	for (auto v_tmp : v) {
		cout << v_tmp.second << " " << v_tmp.first << "\n";
	}
    
    return 0;
}

문제 8. 단어 정렬 (실버 5)

• 문자열의 길이로 먼저 정렬 (map으로 받으면 알아서 오름차순)
• 같은 길이의 문자열을 vector<string>에 받아서 따로 정렬하고 중복은 제거

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> 
#include <map> 

using namespace std;

int main() {
	map<int, vector<string>> m;
	int test_case, str_len, str_len_max=0;
	string str;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		cin >> str;
		str_len = str.length();
		m[str_len].push_back(str);
		if (str_len > str_len_max)	str_len_max = str_len;
	}

	for (int i = 1; i <= str_len_max; i++) {
		sort(m[i].begin(), m[i].end());
		m[i].erase(unique(m[i].begin(), m[i].end()), m[i].end());
	}

	for (int i = 1; i <= str_len_max; i++) {
		for (auto v : m[i]) {
			cout << v << "\n";
		}
	}
    
    return 0;
}

문제 9. 나이순 정렬 (실버 5)

• 위 문제와 비슷하게 map의 키값을 나이로 받고 이름을 vector로 받아 입력받은 순서로 출력

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> 
#include <map> 

using namespace std;

int main() {
    int test_case;
	cin >> test_case;

	int age;
	string name;
	map<int, vector<string>> m;

	for (int i = 0; i < test_case; i++) {
		cin >> age >> name;
		m[age].push_back(name);
	}

	for (auto m_tmp : m) {
		for (auto m_name : m_tmp.second) {
			cout << m_tmp.first << " " << m_name << "\n";
		}
	}
    return 0;
}

문제 10. 좌표 압축 (실버 2)

• 좌표를 입력받은 순서로 기록할 vector와 해당 좌표의 압축값을 기록한 map을 활용

#include <iostream>
#include <vector>
#include <algorithm> 
#include <map>

using namespace std;

int main(){
    int test_case;
	cin >> test_case;

	int tmp;
	map<int, int> m;
	vector<int> v_origin;

	for (int i = 0; i < test_case; i++) {
		cin >> tmp;
		v_origin.push_back(tmp);
	}

    
	vector<int> v_sort(v_origin);
	sort(v_sort.begin(), v_sort.end());
	v_sort.erase(unique(v_sort.begin(), v_sort.end()), v_sort.end());

	for (int i = 0; i < v_sort.size(); i++) {
		m[v_sort[i]] = i;
	}

	for (auto v_tmp : v_origin) {
		cout << m[v_tmp] << " ";
	}
    
	return 0;
}

결과

1. 문제 

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

2. 코드

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ll;

int main() {
    int int_case;
	ll x, y, res,distance, level;
    
	cin >> int_case;

	for (int i = 0; i < int_case; i++) {
		cin >> x >> y;
		distance = y - x;

		if (distance > 0 && distance <= 3) {
			res = distance;
		}
		else {
			level = (int)sqrt(distance);

			if (((level + 1) * (level + 1)) - (level+1) < distance && distance < ((level + 1) * (level + 1))) {
				res = 2 * level+1;
			}
			else if (distance == level * level ) {
				res = 2 * level -1;
			}
			else {
				res = 2 * level;
			}
		}

		cout << res << "\n";
	}
    return 0;
}

3. 결과

4. 문제 풀이 방식

•  가능한 경우의 수를 모두 계산하여 최소의 개수를 찾는 방법 -> 시간 부족으로 인한 실패
•  재귀함수를 작성하여 위와 같은 방식을 구현 -> 구현 실패
•  각 거리 별 결과를 직접 작성하여 패턴을 분석 -> 특정 경우에서 자리수가 증가하는 모습이 보여짐
•  해당 패턴을 기반으로 코드를 작성하여 제출 -> 50%에서 틀림
•  반례를 확인 -> 작성한 코드에선 문제에서 주어진 가장 큰 수 (2147483647)의 처리가 불가
•  자료형을 int -> unsigned long long으로 변경
•  거리가 제곱근의 제곱과 같은 경우 결과에 -1을 해주어야 함
  ex) 거리가 9인경우 제곱근은 3이고, 자리수도 3 (2 * 2 - 1 = 3)
•  아래는 분석한 자료임

문제 1. 블랙잭 (브론즈 2)

#include<iostream>

using namespace std;

int main(){
	int n, m, sum, min, res = 0;
	cin >> n >> m;
	int* card = new int[n];
	bool is_flag;

	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}
	
	sum = 0;
	min = m;
	is_flag = true;
	for (int i = 0; i < n - 1 && is_flag; i++) {
		for (int j = i + 1; j < n && is_flag; j++) {
			for (int k = j + 1; k < n && is_flag; k++) {
				sum = card[i] + card[j] + card[k];
                
				if (sum == m) is_flag = false;
				if (min > m - sum && m >= sum) {
					min = m - sum;
					res = sum;
				}
			}
		}
	}

	cout << res << endl;

    return 0;
}

문제 2. 분해합 (브론즈 2)

#include <iostream>
#include <string>
#include <cmath> 
#include <map> 

using namespace std;

int func_2231_create_decompose(int a) {
	int len, res = a;

	len = to_string(a).length();

	for (int i = len; a > 0; i--) {
		res += a / pow(10, i);
		a %= (int)pow(10, i);
	}

	return res;
}

int main() {
	int a, key;
	cin >> a;

	map<int, int> m;

	for (int i = 1; i < a; i++) {
		key = func_2231_create_decompose(i);
		
		if(!m[key])
			m[key] = i;
	}

	cout << m[a];
    return 0;
}

문제 3. 덩치 (실버 5)

/*
*  문제 내용 이해가 중요한 문제였음.
*  map을 사용해서 구현한 버전
*/

#include <iostream>
#include <map>

using namespace std;

int main() {
    int int_case;
	int cnt, grade;
	int* bulk;

	cin >> int_case;

	map<char, int *> m_input;
	
    // 입력
	for (int i = 0; i < int_case; i++) {
		bulk = new int[2];

		cin >> bulk[0] >> bulk[1];

		m_input['a' + i] = bulk;
	}

	// 등수 : 나보다 덩치가 큰 사람의 수 + 1
	for (int i = 0; i < int_case; i++) {
		cnt = 1;

		for (int j = 0; j < int_case; j++) {
			// 덩치 : 키도 크고, 몸무게도 무거운 사람 수
			if (m_input['a' + i][0] < m_input['a' + j][0] && m_input['a' + i][1] < m_input['a' + j][1]) {
				cnt++;
			}
		}

		// 등수 출력
		cout << cnt << " ";
	}

	for (int i = 0; i < int_case; i++) {
		delete m_input['a' + i];
	}
    
    return 0;
}

/*
*  문제 내용 이해가 중요한 문제였음.
*  2차원 Array를 사용해서 구현한 버전
*/
#include <iostream>

using namespace std;

int main() {
	int int_case, cnt;
	cin >> int_case;
	int** arr = new int*[int_case];
	int* bulk;

	for (int i = 0; i < int_case; i++) {
		bulk = new int[2];
		cin >> bulk[0] >> bulk[1];
		arr[i] = bulk;
	}

	for (int i = 0; i < int_case; i++) {
		cnt = 1;
		for (int j = 0; j < int_case; j++) {
			if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
				cnt++;
			}
		}
		cout << cnt << " ";
	}
    return 0;
}

문제 4. 체스판 다시 칠하기 (실버 5)

#include <iostream>
#include <cstring>

using namespace std;

int func_1018_bitmask(char **_map) {
	int cnt_1 = 0, cnt_2 = 0;
	char filter_1[8][8] = {
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0}
	};
	char filter_2[8][8] = {
		{1, 0, 1, 0, 1, 0, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 0, 1, 0}, 
		{0, 1, 0, 1, 0, 1, 0, 1}
	};

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if ( !(_map[i][j]^filter_1[i][j]) ) {
				cnt_1++;
			}
			if (!(_map[i][j] ^ filter_2[i][j])) {
				cnt_2++;
			}
		}
	}

	if (cnt_1 >= cnt_2) return cnt_2;
	else return cnt_1;
}

int main() {
	int n, m;
	int min, cnt;
	string tmp;
	cin >> n >> m;

	char** tmp_map = new char* [8];
	for (int i = 0; i < 8; i++) {
		tmp_map[i] = new char[8];
	}
	char** bwmap = new char* [n];
	for (int i = 0; i < n; i++) {
		bwmap[i] = new char[m];
	}

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		for (int j = 0; j < m; j++) {
			if (tmp[j] == 'B') {
				bwmap[i][j] = 1;
			}
			else {
				bwmap[i][j] = 0;
			}
		}
	}

	cnt = 0;
	min = 64;
    
	for (int i = 0; i <= n - 8; i++) {
		for (int j = 0; j <= m - 8; j++) {
            
			for (int a = i, aa = 0; a < i + 8; a++, aa++) {
				for (int b = j, bb = 0; b < j + 8; b++, bb++) {
					tmp_map[aa][bb] = bwmap[a][b];
				}
			}
            
			cnt = func_1018_bitmask(tmp_map);
			if (cnt < min) {
				min = cnt;
			}
		}
	}
    
	cout << min << "\n";
    
    return 0;
}

문제 5. 영화감독 숌 (실버 5)

#include <iostream>
#include <cstring>

using namespace std;

int main() {
	int n, cnt=0;
	string tmp;

	cin >> n;

	for (int i = 666; i < 2100000000; i++) {
		tmp = to_string(i);
		if (tmp.find("666") != string::npos) {
			cnt++;

			if (cnt > 10000) break;
			if (cnt == n) {
				cout << tmp << "\n";
			}
		}
	}
}

결과

1. 문제

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

2. 코드

#include <iostream>
#include <cstring>

using namespace std;

bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}


int main() {
    int a, max = 50000000, sum=0;
    bool* arr = Sieve_of_Eratosthenes(max);
    cin >> a;

    for (int i = 0; i <= max; i++) {
        sum += arr[i];
        
        if (sum == a+1) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}

3. 결과

4. 리뷰

• 에라토스테네스의 채 알고리즘을 사용하여 충분히 큰 소수 범위의 소수 여부 배열을 생성함.
• 해당 여부가 1인 경우(소수인 경우)를 누적하여 원하는 위치의 소수를 찾음
• 100점 통과는 가능했지만 좀 더 효율적인 방법이 필요함.

문제 1. 팩토리얼

#include<iostream>

using namespace std;

int func_10872_factorial(int n) {
	if (n == 0) return 1;
	else return n * func_10872_factorial(n-1);
}

int main() {
	int a;
	cin >> a;

	cout << func_10872_factorial(a);
}

문제 2. 피보나치 수 5

#include<iostream>

using namespace std;

int func_10870_fibonacci(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return func_10870_fibonacci(n - 1) + func_10870_fibonacci(n-2);
}


int main() {
	int a;
	cin >> a;

	cout << func_10870_fibonacci(a);
}

문제 3. 별 찍기 -10

문제 4. 하노이 탑 이동 순서

#include<iostream>

using namespace std;

void count_hanoi(int n){
	cout << (1 << n) -1 << "\n";
}

void hanoi(int n, int from, int to) {
	if (n == 1){
		cout << from << " " << to << "\n";
	}else{
		hanoi(n - 1, from, 6 - from - to);
		cout << from << " " << to << "\n";
		hanoi(n - 1, 6 - from - to, to);
	}
}

int main() {
	int n;
	cin >> n;

	count_hanoi(n);
	hanoi(n, 1, 3);
    
	return 0;
}

결과

문제 1. 소수찾기

#include<iostream>

typedef unsigned long long ll;

using namespace std;

int is_prime_number_custom(ll input)
{
    if (input < 2) {
        return 0;
    }

    for (ll j = 2; j <= (ll)(input / j); j++)
    {
        if (input % j == 0)
        {
            return 0;
        }
    }

    return 1;
}

int main() {
    int a, cnt=0;
    cin >> a;
    
    int* arr = new int[a];

    for (int i = 0; i < a; i++) {
        cin >> arr[i];
        if (is_prime_number_custom(arr[i])) {
            cnt++;
        }
    }

    cout << cnt;
    return 0;
}

문제 2. 소수

#include<iostream>

typedef unsigned long long ll;

using namespace std;

int is_prime_number_custom(ll input)
{
    if (input < 2) {
        return 0;
    }

    for (ll j = 2; j <= (ll)(input / j); j++)
    {
        if (input % j == 0)
        {
            return 0;
        }
    }

    return 1;
}
int main() {
    int a, b, min, sum = 0;
    cin >> a >> b;

    for (int i = a; i <= b; i++) {
        if (is_prime_number_custom(i)) {
            if (sum == 0) min = i;
            sum+=i;
        }
    }

    if (sum == 0) cout << -1 << endl;
    else {
        cout << sum << endl;
        cout << min;
    }
    return 0;
}

문제 3. 소인수분해

#include<iostream>

using namespace std;

void func_11653_Factorization(int a) {
    bool is_flag = true;

    for (int i = 2; i < a; i++) {
        if (a % i == 0) {
            is_flag = false;
            cout << i << endl;
            func_11653_Factorization(a / i);
            break;
        }
    }

    if(is_flag) cout << a << endl;
}

int main() {
    int a;
    cin >> a;

    if (a != 1) {
        func_11653_Factorization(a);
    }
    
    return 0;
}

문제 4. 소수 구하기

#include<stdio.h>
#include<math.h>

typedef unsigned long long ll;

int is_prime_number_custom(ll input)
{
    if (input < 2) {
        return 0;
    }

    for (ll j = 2; j <= (ll)(input / j); j++)
    {
        if (input % j == 0)
        {
            return 0;
        }
    }

    return 1;
}

int main() {
    int int_M, int_N;
    scanf("%d %d", &int_M, &int_N);
    
    for(int i = int_M; i <= int_N; i++)
    {
        if(is_prime_number_custom(i)){
            printf("%d\n", i);
        }
    }
    
    return 0;
}

문제 5. 베르트랑 공준

#include<iostream>
#include <cstring> 

using namespace std;

bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

	memset(arr, 1, sizeof(bool) * (m+1));
	arr[0] = false;
	arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    int int_N, cnt;
    bool* arr = Sieve_of_Eratosthenes(123456 * 2);

    do {
        cin >> int_N;
        cnt = 0;
        
        for (int i = int_N + 1; i <= int_N*2; i++)
        {
            if (arr[i]) {
                cnt++;
            }
        }

        if(int_N != 0) cout << cnt << endl;
    } while (int_N != 0);

    return 0;
}

문제 6. 골드바흐의 추측

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    int int_a, int_N, int_sum;
    bool* arr = Sieve_of_Eratosthenes(20000);
    int tmp_a, tmp_b, tmp_min;
    vector<int> v;

    cin >> int_a;
    for (int i = 0; i < int_a; i++) {
        cin >> int_N;

        int_sum = 0;
        v.clear();

        for (int j = 2; j < int_N; j++) {
            if (arr[j]) {
                v.push_back(j);
            }
        }

        tmp_a = 0;
        tmp_b = 0;
        tmp_min = int_N;

        for (int j = 0; j < v.size(); j++) {
            for (int k = 0; k < v.size(); k++) {
                if (int_N == v.at(j) + v.at(k) && tmp_min > abs(v.at(j) - v.at(k))) {
                    tmp_a = v.at(j);
                    tmp_b = v.at(k);
                    tmp_min = abs(v.at(j) - v.at(k));
                }
            }
        }

        if (tmp_a + tmp_b != 0) cout << tmp_a << " " << tmp_b << endl;
    }
    
    return 0;
}

문제 7. 직사각형에서 탈출

#include<iostream>

using namespace std;

int main() {
    int x, y, w, h, min;

    cin >> x;
    min = x;

    cin >> y;
    if (min > y) min = y;

    cin >> w;
    if (min > w-x) min = w-x;

    cin >> h;
    if (min > h - y) min = h - y;

    cout << min;
    return 0;
}

문제 8. 네 번째 점

#include<iostream>
#include<map>

using namespace std;

int main() {
    int a, b;
    map<int, int> x, y;
    map<int, int>::iterator iter;

    for (int i = 0; i < 3; i++) {
        cin >> a >> b;

        if (x.count(a)) x[a]++;
        else x[a] = 1;

        if (y.count(b)) y[b]++;
        else y[b]=1;
    }

    for (iter = x.begin(); iter != x.end(); iter++) {
        if (iter->second == 1) {
            cout << iter->first << " ";
        }
    }

    for (iter = y.begin(); iter != y.end(); iter++) {
        if (iter->second == 1) {
            cout << iter->first;
        }
    }
    
    return 0;
}

문제 9. 직각삼각형

#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int a, b, c;
    int pow_a, pow_b, pow_c, pow_sum;

    while (1) {
        cin >> a >> b >> c;

        pow_a = pow(a, 2);
        pow_b = pow(b, 2);
        pow_c = pow(c, 2);
        pow_sum = pow_a + pow_b + pow_c;

        if (pow_sum == 0)
            break;

        if (pow_a == pow_sum - pow_a || pow_b == pow_sum - pow_b || pow_c == pow_sum - pow_c) {
            cout << "right" << endl;
        }
        else {
            cout << "wrong" << endl;
        }
    }
    
    return 0;
}

문제 10. 택시 기하학

#include<iostream>
#include<cmath>

using namespace std;

double const_pi() {
    return atan(1) * 4; 
}

int main() {
    int r;
    cin >> r;

    // 유클리드 기하학에서의 원의 넓이
    printf("%.6f\n", const_pi() * pow(r, 2));

    // 택시 기하학 에서의 넓이 : 대각선 길이가 2*r인 마름모의 넓이
    printf("%.6f\n", pow(2 * r, 2) / 2);
    
    return 0;   
}

문제 11. 터렛

#include<iostream>
#include<cmath>

using namespace std;

int main() {
    int a;
    cin >> a;

    int x1, y1, r1, x2, y2, r2;
    double len;

    for (int i = 0; i < a; i++) {
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;

        // 두 점 사이의 거리
        len = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));

        // 반경이 완벽하게 겹치면 무한대의 경우
        if (len == 0 && r1 - r2 == 0) {
            cout << -1 << endl;
            continue;
        }

        // 시작점은 같은데 반경이 달라 만날 수 없음
        if (len == 0 && r1 - r2 != 0) {
            cout << 0 << endl;
            continue;
        }

        // 삼각형이 성립되면 2개, 일치하면 1개, 안되면 0개
        if (len < r1 + r2 && r1 < r2 + len && r2 < len + r1) {
            cout << 2 << endl;
        }
        else if (len == r1 + r2 || r1 == len + r2 || r2 == len + r1) {
            cout << 1 << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
    return 0;
}

결과