문제링크 : https://www.acmicpc.net/problem/1735#include using namespace std;typedef long long ll;int A1, B1, A2, B2;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> A1 >> A2 >> B1 >> B2; int a = A1*B2 + B1*A2; int b = A2*B2; int tmp = gcd(a,b); cout 주어진 값에 따라 공통분모와 그에 대한 분수를 구해준다.기약 분수를 구해야하기 때문에 구한 분모와 분수에 대해 최대공약수를 GCD를 통해 구해주고,분모와 분수에 각각 나눠주면 된다.
#include #include #include using namespace std;int solution(string s) { int answer = s.size(); for(int i=1; i=2) result += to_string(cnt) + tmp; //다르면 누적된 문자열(숫자 + 문자) 저장 else result += tmp; //문자만 저장 tmp = s.substr(j, i); //새로운 문자열 시작 cnt = 1; } } // 남은 마지막 문자열 처리 if (cnt >= 2) result += to_string(cnt)..
#include #include using namespace std;vector solution(int k, vector> ranges) { vector answer; vectorv; v.push_back(k); while(k!=1) { if(k%2) k = 3*k +1; else k/=2; v.push_back(k); } for(auto range : ranges) { int s = range[0]; int e = v.size()-1 + range[1]; double tmp = 0; for(int j=s; j e) answer.push_back(-1.0..
문제링크 : https://www.acmicpc.net/problem/1011#include using namespace std;typedef long long ll;int T;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> T; while(T--) { ll x, y; cin >> x >> y; ll gap = y-x; double n = sqrt(gap); int n2 = round(sqrt(gap)); if(n 먼저 거리에 따른 규칙을 찾아봐야 한다.거리 형태 횟수1 1 12 11 23 111..
#include #include using namespace std;void hanoi(int n, int go, int to, vector>&v){ if(n==1) //원판이 1개인 경우 (성공 케이스) { v.push_back({go, to}); return; } hanoi(n-1, go, 6-go-to, v); //n-1개의 원판을 보조(중간) 기둥으로 옮김 hanoi(1, go, to, v); //가장 큰 원판을 목표 기둥으로 옮김 hanoi(n-1, 6-go-to, to, v); //n-1개의 원판을 보조(중간) 기둥에서 목표 기둥으로 이동}vector> solution(int n) { vector> answer; ha..
문제링크 : https://www.acmicpc.net/problem/1744#include using namespace std;typedef long long ll;int N;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; vectorvp, vm; for(int i=0; i> num; if(num > 0) vp.push_back(num); else vm.push_back(num); } sort(vp.begin(), vp.end(), greater()); sort(vm.begin(), vm.end()); int result = 0; for(int ..
문제링크 : https://www.acmicpc.net/problem/1715 #include using namespace std;typedef long long ll;int N;int arr[100001];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; int tmp, answer = 0; priority_queue, greater> pq; for(int i=0; i> tmp; pq.push(tmp); } while(!pq.empty()) { int sum = 0; sum += pq.top(); //합칠 첫번째 수 pq.pop..
문제링크 : https://www.acmicpc.net/problem/6603#include using namespace std;typedef long long ll;int k, arr[13], ans[6];void dfs(int s, int idx){ if(idx == 6) { for(int i=0; i> k) { if(k==0) break; for(int i=0; i> arr[i]; dfs(0, 0); cout 백트래킹을 활용한 문제이다.시작점과 현재 인덱스를 같이 넘기고, 인덱스가 6이 되는 순간을 체크하여 저장된 배열 값들을 출력해준다.배열 값 저장 같은 경우 기존에 입력받은 값들을 idx 값에 따라 정답 배열에 저장..
#include #include#include using namespace std;int solution(vector> board){ int answer = 0; for(int i=1; i 현재 값을 기준으로 직전 3가지 값을 체크한다 (board[i-1][j-1], board[i-1][j], board[i][j-1])해당 3가지 값들의 최소값을 기준으로 + 1한 값을 현재 위치에 저장해준다.이는 모든 값이 1로 이루어진 정사각형 여부를 판별하는 것이다.만약 하나라도 0인 값이 존재하면 0+1로 1을 그대로 유지하게 된다. 이를 누적하여 더하며 이어진 정사각형 크기를 판별하고, 이렇게 저장한 값은 한 변의 길이가 된다.따라서 최종 출력은 제곱을 하여야한다.
#include #include #include #include using namespace std;int dy[] = {0, 0, 1, -1};int dx[] = {1, -1, 0, 0};bool bfs(int y, int x, vectorv){ vector> visited(5, vector(5, false)); queue> q; q.push({y, x, 0}); visited[y][x] = 1; while(!q.empty()) { auto [yy, xx, dist] = q.front(); q.pop(); if(dist == 2) continue; //맨해튼 거리 2이내만 탐색 for(..
#include #include #include using namespace std;int solution(int n, int k, vector enemy) { int answer = enemy.size(); //모든 라운드 버팀 상정 priority_queue, greater> pq; for(int i=0; i k) { n -= pq.top(); //병사 사용 pq.pop(); } if(0 > n) //병력 소진 { answer = i; break; } } return answer;} 우선순위 큐를 활용한 문제이다...
#include #include #include using namespace std;int column;bool cmp(vector&v1, vector&v2){ if(v1[column] == v2[column]) return v1[0] > v2[0]; return v1[column] > data, int col, int row_begin, int row_end) { int answer = 0; column = col-1; sort(data.begin(), data.end(), cmp); for(int i=row_begin; i 주어진 조건을 차근차근 풀면 되는 문제이다.다만 인덱스를 주의해서 풀어주어야 한다. col 번째 컬럼의 값을 기준으로 정렬 할 때, ..
#include #include #include using namespace std;int dy[] = {0, 0, 1, -1};int dx[] = {-1, 1, 0, 0};int visited[101][101];int solution(vector board) { int answer = -1; queue>q; for(int i=0; i= board[0].size() || ny >= board.size()) break; //범위 밖 if(board[ny][nx] == 'D') break; //장애물 } ny -= dy[i]; //부딪히기 바로 전으로 nx -= dx[i]; ..
문제링크 : https://www.acmicpc.net/problem/2529#include using namespace std;typedef long long ll;int n;char arr[11];bool visited[11];string max_s = "";string min_s = "9876543210";void dfs(string s){ if(s.size()==n+1) { max_s = max(max_s, s); min_s = min(min_s, s); return; } for(int i=0; i' && s.back()-'0'i) continue; visited[i] = 1; s.push_back(i+'0'); ..
문제링크 : https://www.acmicpc.net/problem/10971#include using namespace std;typedef long long ll;int n, answer = INT_MAX, start;int arr[11][11];bool visited[11];void dfs(int idx, int cost, int depth){ if(depth==n-1) //최대 깊이 도달 { if(arr[idx][start]) { answer = min(answer, cost + arr[idx][start]); return; } } for(int i=0; i> n; for(int i=0; i>..