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..
최대 6자리 숫자의 자리수 중에 2개를 고르는 것: 6C2 =15가지 최대 10번 자리 교환한다 15의 10승=> 시간초과 따라서 VISIT방문 처리를 해주거나 다른 방법으로 풀어야되는데 다른 사람걸 보고 VISIT[만든숫자][교환횟수]=TRUE 이런식으로 해주면 된다. 백준의 토마토 3차원문제가 이런식으로 했던거 같은데 가끔 잊을만하면 나온다 #include #include #include #include using namespace std; int result; bool visit[1000000][11]; int toNumber(string s){ int temp=0; for(int i=0;iresult)result=temp; return; } for(int i=0;it; for(int tc=1;tc..
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 커서 (현재 보고 있는 위치)에 동적으로 추가 삭제, 그리고 링크 이동을 연습하는 문제 #include #include #include #include using namespace std; int t; string s; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; while (t--) { list li; ci..
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 두 가지 방법으로 풀 수 있다. 하나는 원소 체크(기록)을 해서 배열의 원소 a에 대해서 x-a가 배열에 있는 지 체크하는 법 또 하나는 정렬 후 투포인터를 이용하는 법. 1. 기록 #include using namespace std; int num[100001]; int cnt[2000001]; int main(void) { ios::syn..
https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net #include #include #include using namespace std; int num[26]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; for (auto c : s) { num[c - 'a']++; } cin >> s; for (auto c : s) { n..
https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 9의 경우는 6인 것처럼 카운팅해준다. 0부터 9까지 몇 개 나왔는지 확인하고 6은 6과 9의 카드 모두 쓸 수 있으니 2로 나눠서 몇 팩이 필요한지 본다. 만약 6이 홀수로 남으면 한 팩이 더 필요하므로 +1 해준다. 나머지 숫자는 한 팩당 카드 하나씩 있으므로 카운팅한 갯수가 필요한 팩의 수이다. 각 숫자가 필요한 팩의 개수 중 가장 큰 수가 답이다. #include #include using namespace std; int num[10]; int main(void) { ios::..