https://www.acmicpc.net/problem/20183 20183번: 골목 대장 호석 - 효율성 2 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 이분 탐색을 통해 특정 비용 이하의 도로만 이용하면서 현재 가진 돈을 가지고 목적지까지 이동할 수 있는지 확인하는 방법으로 문제를 해결했다. 이때 가진돈을 가지고 목적지까지 갈 수 있는지 판단하는 방법은 다익스트라를 이용했다. 즉 다익스트라를 이용해 이동하면서 특정 비용 이하의 도로만 이동할 수 있도록 제한했다. 코드 #include #include #incl..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 전체 단어에 나온 알파벳을 vector alpha에 저장해 놓은 뒤, sort(alpha.begin(), alpha.end()); alpha.erase(unique(alpha.begin(), alpha.end()), alpha.end());을 통해 중복된 알파벳을 지우고, 해당 알파벳이 몇 번째 인덱스에 위치하는지 저장해 놓았다(map alpha_index). 그리고 각 알파벳에 부여할 숫자..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 입력되는 수들의 가장 작은 수에서 중앙값의 수 범위의 수들은 최대 힙에 저장하여 해당 힙의 top에 중앙값이 위치하도록 하고, 중앙값보다 큰 범위의 수들은 최소 힙에 저장하여 해당 힙의 top에 중앙값보다 큰 수중에서 가장 작은 값이 위치하도록 하여 중앙값을 관리하는 방법으로 문제를 해결했다. 코드 #include #include #include #include using name..

https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 모든 식재료를 확인하며 해당 식재료를 고르는 경우와 고르지 않는 경우를 완전 탐색(브루트 포스)하여 문제를 해결했다. 이때 조건을 만족하고 이전의 최소 비용과 같은 최소비용을 찾았다면 사전 순으로 앞서는 것을 골라야 하는데, 이때 백터끼리 대소 비교로 사전 순으로 앞서는 것을 판별했다. 코드 #include #include #include using namespace std; int n; int..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2차원 누적합을 이용해서 문제를 해결했다. 코드 #include #include using namespace std; int n, m; int board[1030][1030]; int psum[1030][1030]; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m; f..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 맵에서 0으로 표시된 위치들 중 인접한 구역들을 하나로 공간으로 묶어서 공간 id로 부여하고, 공간 id의 크기를 저장한다. 그리고 벽인 위치들을 확인하며 해당 벽의 인접한 공간 id들을 확인하고 그 공간 id들의 크기와 해당 벽의 위치까지 고려하여 문제를 해결했다. 코드 #include #include #include #include using namespace std; i..