#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>..
문제링크 : https://www.acmicpc.net/problem/10974#include using namespace std;typedef long long ll;int n;int arr[9];bool visited[9];void dfs(int idx){ if(idx==n+1) //최대 깊이 도달 { for(int i=1; i> n; dfs(1); return 0;} 기본적인 백트래킹 문제이다.배열에 백트래킹을 통한 순열 순서를 담아준다.이후에 깊이가 n에 도달했을 때 해당 배열을 출력해주면 된다.
문제링크 : https://www.acmicpc.net/problem/10819#include using namespace std;typedef long long ll;int n, max_n;int arr[8], perm[8];bool visited[8];void dfs(int idx){ if(idx==n) //최대값 계산 { int sum = 0; for(int i=0; i> n; for(int i=0; i> arr[i]; dfs(0); cout 백트래킹을 이용해 푸는 문제이다.먼저 처음 위치인 0부터 시작하여 최대 idx가 n에 도달할 때 해당 조합에 대한 차이 값을 계산하며 최대값도 비교해준다. 조합하는 과정은 방문 배열을 통해 현재 숫자가 선택..
#include #include using namespace std;int arr[101][101];int cal(int x1, int y1, int x2, int y2){ int min_num = arr[x1][y1]; int tmp = arr[x1][y1]; //시계 반대방향에서 끌어오기 for(int i=x1; ix1; i--) { arr[i][y2] = arr[i-1][y2]; min_num = min(min_num, arr[i][y2]); } for(int i=y2; i>y1; i--) { arr[x1][i] = arr[x1][i-1]; min_num = min(min_num, ..
#include using namespace std;typedef long long ll;int n;vectorv;void dfs(ll num){ if(num > 9876543210) return; v.push_back(num); for(int i=0; i i) { dfs(num*10+i); } }}int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i=0; i 재귀를 통해 풀 수 있는 문제이다.처음에 기본 시작인 0~9까지를 dfs로 돌려준다.여기에 이어서 숫자를 하나씩 붙여주는데,num%10>i 조건문을 통해 숫자의 마지막 ..
#include #include #include #include using namespace std;long long cal(long long a, long long b, char op){ if(op == '+' ) return a+b; else if(op == '-') return a-b; else return a*b;}long long solution(string expression) { long long answer = 0; vectorv = {'*', '+', '-'}; vectornum; vectorop; string tmp = ""; for(int i=0; i= '0' && expression[i] num2 = num; ve..
문제링크 : https://www.acmicpc.net/problem/1063#include using namespace std;//R, L, B, T, RT, LT, RB, LBmap m = { {"R", 0}, {"L", 1}, {"B", 2}, {"T", 3}, {"RT", 4}, {"LT", 5}, {"RB", 6}, {"LB", 7}};int dy[] = {0, 0, -1, 1, 1, 1, -1, -1};int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); string king, stone; int n; cin>> king >> st..
#include #include #include #include using namespace std;bool check(string tmp){ stackst; for(auto i : tmp) { if(i == '(') st.push(i); else { if(st.empty()) return false; //올바르지 않은 문자열 st.pop(); } } return st.empty();}string solution(string p) { string answer = ""; string u = "", v = ""; if(p.empty()) return p; // 조건 1 ..
문제링크 : https://www.acmicpc.net/problem/1057#include using namespace std;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n, a, b, cnt = 0; cin >> n >> a >> b; while(a!=b) { a = (a+1)/2; b = (b+1)/2; cnt++; } cout 각 값들을 2로 나누면서 같아지는 순간을 체크한다.다만 단순히 2를 나누는 것이 아니라 1을 더해주어야 한다.7, 8을 예시로 들면 7/2 = 3, 8/2 = 4 이기에 둘 다 같은 4를 반환하려면 1을 더해줄 필요가 ..
#include #include using namespace std;vector solution(int n, long long k) { vector answer, v; vector fac(n, 1); //팩토리얼 계산 for (int i = 1; i = 0; i--) { int idx = k / fac[i]; //위치 answer.push_back(v[idx]); v.erase(v.begin() + idx); //찾은 값 삭제 k %= fac[i]; //k값 조정 } return answer;} 먼저 가능한 케이스를 통해 규칙을 찾아보자.1 : 12 : 1 2 / 2 13 : 1 2 3 / 1 3 2 / 2 1 3 /..
문제링크 : https://www.acmicpc.net/problem/1058#include using namespace std;int dist[51][51];int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n, result = 0; cin >> n; for(int i=0; i> s; for(int j=0; j 플로이드 - 워셜 알고리즘을 통해 풀 수 있는 문제이다.먼저 배열을 최대값으로 지정하고, 이후에 'Y' 값을 기준으로 해당 거리 ij에 대해서 초기 거리 1을 설정해준다. 이제 플로이드 워셜 알고리즘을 통해서 가능한 케이스에 대해 거리를 갱신해준다.거리를 갱신했으면 이제 가장 2-친구의 수..