그린푸딩

https://www.acmicpc.net/problem/1208 부분수열이란게 뭘 연속된걸 말하는지 뭔지 헷갈려허 해맸다그니까 최대 40개중 2^40 으로 그냥 고르면 되는거였다다만 2^40 = 1억이 넘어가서 2^20으로 따로따로 부분수열 구해서 합의 결과를 저장한다. 부분 수열 구하는건 비트마스킹으로 조합을 구한다. 그리고 한가지 두개로 쪼갠거에 비트마스킹해서 둘다 아무것도 안골랐을때가 합이 0인경우에 포함되서 0일 경우에만 1을 빼주면된다#include #include #include #include#include#include#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); ..

옛날에 푼건데.. 투포인터 -> 정렬 후 끝에서 내려와야 반복 안함메모리 초과조심 #include #include #include #include#include#include#includeusing namespace std;//s->e//경로중에 최솟값이 최대로 int len = 1e9;unordered_mapanum;unordered_mapbnum;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t, n, m; vectorA; vectorB; vectora; vectorb; cin >> t; cin >> n; A.assign(n, 0); for (int i = 0; i > A[i]..

주의할점 - visited를 map으로 루프 내부에 하면 정렬 시간이 든다 - 던순 bfs로 풀었는데, 이렇게 큐에서 모든 문자열을 들게하면 string 생성+ 복사비용이 들어서 별개의 배열로 역추적해서 하면 시간이 더빨라진다. 문자열 더하는게 새로운 메모리 공간에 옮겨서 더해짐 #include #include #include #include#include#include#includeusing namespace std;int cmdD(int num) { int tmp = num * 2; if (tmp > 9999)tmp %=10000; return tmp;}int cmdS(int num) { int tmp = num - 1; if (tmp == -1)tmp = 9999; ..

https://www.acmicpc.net/problem/1600 상태를 잘 다뤄야하는 bfs문제이다. 처음에 2차원 배열로만 visited 방문 처리를 했는데, 최단거리로 점프 다 써서 왔는데 마지막이 하필 점프로만 갈수 있는 경우, 이미 지나온 길을 방문처리해서 느리게라도 갈 수 있는 경우를 제외한다. 그래서 같은 횟수로 여길 왔는가?로 방문처리를 해줘야한다#include #include #include #include#include#includeusing namespace std;typedef pairci;int k;int w, h;int visited[200][200][31];vector>arr;struct info { int r; int c; int knum = 0;};//격자이..

https://www.acmicpc.net/problem/17835 도시 -> 모든 면접장 다익스트라를 을 모든 도시(x10만)하면 터진다 면접장 -> 도시로 하면 딱 도로 갯수 만큼 거리가 갱신되는데, 그이유는 한번 제일 짧은 거리가 정해지면 그 정보를 나머지 면접장끼리 한 큐에 있으니 공유를 하니 가지 않는다. 정방향 다익스트라는 이정보를 공유하지 않으니 x10만이지만, 역방향으로 하면 한번에 끝낼 수 있다#include #include #include #include#include#includeusing namespace std;typedef pairci;vectorarr[100001];long long INF = 2e10;int main() { ios::sync_with_stdio(fals..

https://www.acmicpc.net/problem/1947 점화식 떄려맞췄는데 맞았다..ㅋㅋㅋn번째 애가 (1...n-1 중에 한명꺼를 취할 경우) =n-11) 취해진 선물 가져온 애가 n번째애꺼 선물 가져가는경우 = dp[n-2]2) 취해진 선물 가져온 애가 n번째애꺼 선물 안가져가는경우 -> 똑같이 n선물이 k의 선물인것처럼 취급해서 n-1끼리 배분하는것 =dp[n-1]최종적으로 (n-1)x(dp[n-1]+dp[n-2]) 이다.#include #include #include #include#include#includeusing namespace std;long long dp[1000001];int main() { ios::sync_with_stdio(false); cin.tie(NU..

https://www.acmicpc.net/problem/5214 시간,메모리 초과에 주의해야하는 문제 연결정보 일반적으로 모든 정점 x 모든 정점인데 여기선 그렇게 하면 터진다 각 정점이 속한 튜브 정보를 저장하고(mxk) 탐색해야한다 #include #include #include #include#include#includeusing namespace std;//mC2 x k 으로 저장하면 터짐//튜브별 번호 넣어서 mxk vectortube[1001];vectormytubeinfo[100001]; //주의int main() { ios::sync_with_stdio(false); cin.tie(NULL); //1-> 번역 int n, m, k; cin >> n >> k ..

https://www.acmicpc.net/problem/1525' dfs로 풀다가 생각해보니 dfs로 풀면 처음 나온게 답이 아닐 수 있다... bfs로 풀면 처음 답인게 최소횟수로 방문한것이다 #include #include #include #include#include#includeusing namespace std;unordered_mapvisited;vector>arr;vector>ans = { {1,2,3},{4,5,6},{7,8} };int dr[4] = { 0,0,-1,1 };int dc[4] = { 1,-1,0,0 };string makestring(vector>arr) { string tmp = ""; for (int i = 0; i >arr; int zr; int..

초기값을 무조건 반영하면 안되는것에 주의break 주의 #include #include #include #include#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); //행복도 가장 작은거 //피로도 가장 큰거 long long mins = 1e9; long long maxs = 0; int n; cin >> n; long long a, b; int cnt = 0; vectorhappymin; vectorhappymax; vectortiredmin; vectortiredmax; happymin.assign(n + ..

행을 한줄만 가지고 내려가기.. nxn인지 알고 한참 해멧다#include #include #include #include#includeusing namespace std;//왼아 아 오아 int dr[3] = { 1,1,1 };int dc[3] = { -1,0,1 };int arr[3];int maxs[3];int mins[3];int tmax[3];int tmin[3];int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 0; i > arr[j]; if (i == 0) { mins[j] = arr[j]; ..