#include #include #include #include using namespace std;int dy[] = {0, 0, 1, -1};int dx[] = {1, -1, 0, 0};int visited[101][101];vector solution(vector maps) { vector answer; for(int i=0; i>q; q.push({i, j}); visited[i][j] = 1; int sum = maps[i][j]-'0'; //누적합용 변수, 시작 값 저장 while(!q.empty()) { auto [y, x] = q.front(); ..
#include #include #include #include #include using namespace std;string change(string in) { string out = ""; map m = { {"A#", 'H'}, {"B#", 'I'}, {"C#", 'J'}, {"D#", 'K'}, {"E#", 'L'}, {"F#", 'M'} }; //#을 대응되는 문자로 변환 for (int i = 0; i musicinfos) { string answer = "(None)"; int time = 0; //변환 m = change(m); for (int i = 0; i parts; string part..
#include #include #include using namespace std;int solution(vector players, int m, int k) { int answer = 0; queue q; for (int i = 0; i queue를 활용해 풀 수 있는 문제이다.우선 현재 플레이어 수와 m 값 기준으로 필요한 서버 수를 계산해준다.그리고 해당 문제에서 queue에 서버 수를 담아줄 것이므로 queue의 사이즈는 작동 중인 서버 수가 될 것이다. 이제 운영중인 서버수와 필요한 서버 수의 차이를 구해 추가해야할 서버 수가 몇개인지 구해주고, 이를 answer에 누적하여 더해준다.이제 추가된 서버 수 만큼 해당 서버의 종료시간을 queue에 넣어주자.매 반복문마다 처음에 ..
#include #include #include using namespace std;vector>v[51];vectordist;void Dijkstra(){ priority_queue, vector>, greater>>pq; pq.push({0, 1}); dist[1] = 0; while(!pq.empty()) { auto [cost, cur] = pq.top(); pq.pop(); for(int i=0; i cost + ncost) { dist[next] = cost + ncost; pq.push({dist[next], next}); ..
#include #include #include #include using namespace std;map m;void cal(string order, string tmp, int idx, int target) { if (tmp.size() == target) { m[tmp]++; return; } for (int i = idx; i solution(vector orders, vector course) { vector answer; for (auto& order : orders) sort(order.begin(), order.end()); for (auto i : course) { m.clear(); ..
#include #include #include #include using namespace std;int dy[] = {0, 0, 1, -1};int dx[] = {1, -1, 0, 0};int solution(vector maps) { int answer = -1; bool flag = false; int y = 0, x = 0; queue>q; vector> v(maps.size(), vector(maps[0].size(), 0)); for(int i = 0; i= maps[0].size() || ny = maps.size()) continue; if(maps[ny][nx] != 'X' && v[ny][nx] == 0) //X 여부 ..
#include #include #include using namespace std;int solution(vector arrayA, vector arrayB) { int answer = 0; int Anum = accumulate(arrayA.begin(), arrayA.end(), 0, gcd); int Bnum = accumulate(arrayB.begin(), arrayB.end(), 0, gcd); answer = max(Anum, Bnum); if(answer == Anum) { for(auto i : arrayB) { if(i % answer == 0) return 0; } } else ..
#include #include using namespace std;string solution(int n) { string answer = ""; char c[3] = {'4', '1', '2'}; while(n > 0) { int r = n % 3; answer = c[r] + answer; n /= 3; if(r == 0) n--; } return answer;} 3진법 계산을 응용한 문제이다. 이번 문제는 기존의 0, 1, 2가 아닌 아래와 같이 4, 1, 2를 나머지로 갖는다.n%3==0 : 4 / n%3==1 : 1 / n%3==2 : 2 따라서 이를 토대로 ans..
#include #include #include #include using namespace std;int solution(vector> book_time) { int answer = 0; vector>v; for (auto i : book_time) { int s = stoi(i[0].substr(0, 2)) * 60 + stoi(i[0].substr(3, 2)); int e = stoi(i[1].substr(0, 2)) * 60 + stoi(i[1].substr(3, 2)) + 10; v.push_back({s, e}); } sort(v.begin(), v.end()); priority_queue, greater> pq;..
#include #include #include using namespace std;long long solution(vector weights) { long long answer = 0; mapm; for(int i=0; i=2) answer += (m[i] * (m[i]-1)) / 2; } return answer;} 문제에 주어진 경우의 수를 보면 (2, 3), (1, 2), (3, 4) 이렇게 3가지 케이스에 대해 검토해야 한다는 것을 알 수 있다.같은 숫자 조합의 경우 조합 공식으로 갯수를 알 수 있기에 1개 이상인 경우를 찾기 위해 map으로 카운팅을 해주었다. 이후에는 현재 수를 기반으로 2로 나눠지면 2:3 비율 값이 Map에 있는 지 체크,3으로 나눠지면..
#include #include #include #include #include using namespace std;vector v[101];bool visited[101];int dfs(int cur) { visited[cur] = 1; int cnt = 1; //카운팅 for (int next : v[cur]) { if (visited[next]) continue; cnt += dfs(next); } return cnt;}int solution(int n, vector> wires) { int answer = INT_MAX; for (auto wire : wires) { v[wire[0]].push_back(w..
문제링크 : https://www.acmicpc.net/problem/17291#include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int dp[20];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[0] = dp[1] = 1; //초기값 for(int i=2; i 기본적으로 매년 분열하므로, dp식을 매번 직전 값에 2배를 해준다.이후 감소되는 케이스를 보면, 짝수년도 4번 분열 + 홀수년도 3번 분열이므로 사실상 짝수년도에서만 분열되었던 값들이 사라지게 되는 것을 알 수 있다. 이에 4번 ..
문제링크 : https://www.acmicpc.net/problem/17391 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, M;int arr[301][301];bool visited[301][301];int dx[] = {0, 1};int dy[] = {1, 0};void bfs(){ queue>q; q.push({0, 0, 0}); visited[0][0] = 1; while(!q.empty()) { auto [y, x, cnt] = q.front(); q.pop(); if(y == N-1 && x == M..
문제링크 : https://www.acmicpc.net/problem/6571dp = [0 for i in range(1001)]dp[1] = 1dp[2] = 2for i in range(3, 1001) : dp[i] = dp[i-1] + dp[i-2]while(True): a, b = map(int,input().split()) if a == 0 and b == 0 : break cnt = 0 for i in range(1, 1001) : if a 피보나치 계산에 따라 수가 매우 커지므로 python으로 푸는 것이 용이한 문제이다.C++로 풀 경우 문자열로 바꾸어서 계산할 필요가 있다. 이외에는 사전에 피보나치를 dp를 통해 미리 계산해놓고 입력받은..
문제링크 : https://www.acmicpc.net/problem/14607#include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;ll N;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; cout 백준 14606번과 유사하지만 N의 범위 때문에 14606번을 풀었던 점화식을 그대로 사용한다면 메모리 초과가 발생하는 문제이다.참고링크 : https://blob-thinking.tistory.com/386 [백준 14606번] 피자 (Small) (C++)문제링크 : https://www.acmicpc.net/pr..