풀이 참고 https://yabmoons.tistory.com/319 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define endl "\n" #define MAX_N 10001 using namespace std; typedef struct st { int num; int parent; int child[2]; int index;//몇 번째 자식인지 판별 }Node; int v, e, a,b, ancestor, subsize; int dist[MAX_N][2]; Node tree[MAX_N]; void init() { memset(dist, 0, sizeof(dist)); for (int i = 0; i < MAX_N; i..
뒤에서부터 한 문자씩 끊어서 vector에 저장한 다음 사전순 정렬했다 #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include using namespace std; int t,k; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; string s; for (int tc = 1; tc > k; cin >> s; vector list; string tmp = ""; for (int i = s.length()-1; i>=0; i--) { tmp = s[i]+tmp; list.push_back(tmp); } sort(list.begin(), list.end()); cout
연결리스트를 구현을 하면 좋으련만 c++을 다시 공부하면서 stl도 아직 모르는게 많아서 문제 많이 풀면서 익숙해지는게 먼저인 것 같다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); for (int tc = 1; tc > n; // 암호문 길이 for (int i = 0; i > x; l.push_back(x); } cin >> n; //명령어 개수 while (n--) { cin >> tmp; if (tmp == 'I') { cin >> x >> y; auto ite..
어느 점에서 시작하는게 가장 긴 거리인지 모르므로 모든 점을 다 돌려본다. DFS로 최대 들어갈 수 있는 깊이까지 들어간다고 보면 된다. BFS써도 될거 같긴 하다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include using namespace std; int n, m,t; vector v[11]; bool vis[11]; int ans; void dfs(int cnt,int num) { if (cnt > ans)ans = cnt; for (int i = 0; i < v[num].size(); i++) { int next = v[num][i]; if (!vis[next]) { vis[next]=true; dfs(cnt + 1, ne..
행을 이동하면서 각 열에 퀸을 놔본다. #include #include using namespace std; int t,n; int col[11];// 각 행에 놓는 열의 위치를 저장한다 int cnt; bool check(int row) { for (int i = 0; i < row; i++) { if (col[i] == col[row] || abs(col[row] - col[i]) == row - i) {// 기울기가 판단 return false; } } return true; } void queen(int row) { if (row == n) {//모든 퀸 다 놓음 cnt += 1; return; } for (int j = 0; j < n; j++) {//놓을 열을 선택 col[row] = j; /..
a -> b 방향으로 화살표가 있다면 a가 작업된 후에 b를 작업할 수 있다는 이야기 edge[a]에는 b를 추가해주고 cnt[b]는 1증가시킨다. (b로 들어오는 간선개수라고 생각해준다) 사전작업(간선)이 없는 곳, 즉 cnt[해당작업번호]=0인 곳부터 출력해준다. dfs의 경우는 방문 배열 처리를 해준다. bfs는 0인 곳을 큐에 먼저 다 넣어줄 수 있어서 필요없다. 현재 방문한 곳 cur와 연결된 곳의 간선의 수를 하나 줄여주고 (사전작업이 하나 줄었으니까!) 연결된 곳의 cnt[다음정점번호]가 0이 된다면 방문할 수 있다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include #include using namespace std;..
묶음의 개수 P가 정해졌을 때 각 묶음의 달란트를 곱한 수가 크려면 각 묶음의 달란트가 최대한 골고루 분배되어야 된다는 것을 알 수 있다. 일단 달란드 개수 N/P는 각 묶음의 최소 달란트 개수로 초기화해준다. 그러면 N%P만큼의 분배되지 않은 달란트가 남을 것인데 해당 달란트들은 골고루 +1씩 해줘서 나눠준 후 곱하면 된다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include using namespace std; int n, t, p; long long ans; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; for (int tc = 1; tc > n >..
n개의 자성체들 사이에는 n-1개의 균형점이 무조건 존재한다고 보고 양 자성체들을 각각 s,e로 놓고 균형점(mid)의 위치를 이분탐색으로 찾아나간다. 오차범위가 무슨 말인지 못하다가 대략 이해했는데 만약 이분탐색으로 양쪽의 힘이 딱 같은 곳을 못발견한채로 s>e가 되어버리는 순간이 있다면 균형점 mid를 찾아야되는데 범위를 넘어가버린다는 것은 이분탐색으로 정확히는 모르지만 s와 e사이에 균형점이 있기는 있다는 것이다. 그럼 세부 좌표 오차일 것이므로 해당 mid를 출력해버리면 된다. s에 1e^12를 빼거나 e에서 뺐을 때 범위를 넘어가면 두 좌표 사이의 거리는 그것보다 작은 것이니까 그 사이에 무조건 있다. 그래도 mid를 출력해도 되는 이유는 10자리까지만 출력하기 때문인 것 같다. #include..
입력받은 문자열의 실제 숫자 개수를 배열에 저장한다 (인덱스 = 숫자) 숫자 개수만큼 다시 문자열 형태로 출력해준다. #include #include using namespace std; int t; int getNum(string str) { if (str == "ZRO")return 0; if (str == "ONE")return 1; if (str == "TWO")return 2; if (str == "THR")return 3; if (str == "FOR")return 4; if (str == "FIV")return 5; if (str == "SIX")return 6; if (str == "SVN")return 7; if (str == "EGT")return 8; else return 9; } s..
일단 1~18 사이 소수를 먼저 구해준 후 A가 소수 개를 성공할 확률, B가 소수 개를 성공할 확률을 구한다. 만약 A가 2개를 성공한다고 칠 때 18개의 구간 중 어느 구간 2개에서 성공하는 지를 구해줘야 하므로 18C2를 구해서 a의 2개 성공확률에 곱해줘야 된다. 둘 중 적어도 하나가 소수인 확률은 전체확률인 1에서 둘다 소수가 아닌 확률(여집합)을 빼주면 된다. 교집합을 구하는 방법과 소수개를 성공할 확률을 구하는 것까지는 잘 했는데 조합을 구해줘야 된다는 것을 떠올리지 못해 못 풀어서 해당 부분은 참고해서 했다. 조합은 nCr=n-1Cr-1 +n-1Cr의 식을 참고하여 이중배열로 미리 구해준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #inc..