나 요리학원 출신임

문제의 조건이 많다 정리하자면1) 학교는 N개이고, 학생은 A[i]...A[N]명2) 대회의 팀은 1~200000까지 임의로 가능3) 대회에 나가려면 같은 학교 학생끼리 팀을 해야함4) 학교에서 대회를 나가려면 모든 학생이 팀에 포함되어 나가야 함5) 학교 예선 1등만 본선에 가고 본선은 최소 2팀이상 나와야 함 대회에 나가려면 학교 학생의 공약수로 팀을 이뤄야 한다그래야 모든 학생이 나갈 수 있다그럼 모든 학교의 공약수를 미리 구해두고 공약수 X 공약수를 가지는 학교의 최대값을 찾으면 된다!이 때 공약수를 가지는 학교가 2이상만 가능하다 200만 X 20만 ==롱롱 필수벡터로 구현했다가 메모리 터졌다 ㅎㅎ 소스코드1234567891011121314151617181920212223242526272829#..

모든 꼭짓점 (x,y)에 대해, 이 점을 공유하는 넓이가 같은 사각형의 수를 세는 문제다. 쉽게 푼 사람들은 쉽게 푼거같은데.. 난 더럽게 푼거같다 처음에 map만 써야되는데 아무 의미없는 set도 같이 써서 시간초과가 났다 문제는 꼭짓점 x,y를 정하고 그 점을 중심으로 양쪽 대각선 방향으로 넓이를 비교해주면 된다! 1) 왼쪽 위, 오른쪽 아래2) 오른쪽 위, 왼쪽 아래 이렇게 두번 보면 된다 위에있는 값들을 map에 넣고 수를 센다그리고 아래있는 값들이 map에 들어 있다면 답에 더해준다! 넓이를 구하는건 펜윅트리를 사용했다..! 그냥 배열로도 구할 수 있지만 갑자기 쓰고싶어서..! 소스코드12345678910111213141516171819202122232425262728293031323334353..

알파벳 최대 26개가 들어올 때 3글자가 일직선인 것의 수를 찾는 문제다진짜 직선만 완탐으로 다봤는데 바로 틀리더라문제를 푸는 방법은 CCW 였다....!잊고있었다 CCW.. 점 3개를 줄 때 직선이면 0을 리턴하므로 그걸로 답을 세면 된다 소스코드123456789101112131415161718192021222324252627282930313233#include #include #include using namespace std;int n;char arr[111][111];vector vt; bool ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int ret = x1*y2 + x2*y3 + x3*y1; ret -= (y1*x2 + y2*x3 + y3*..

N마리의 점소, N마리의 점 없는 소가 있고 각자 M개의 유전자를 가지고 있다이 때 M개중 3개를 골라서 비교했을 때 점O소와 점X소를 비교 가능한 줄이 몇개 있는지 찾는 문제다! set을 이용해서 완탐을 했다!점O소 의 DNA M개중 몇 번째 줄을 볼지 정하고 그 값들을 모두 set에 넣어버린다 그리고 점X소 중 만약 set에 있는 값을 가지고 있는 것이 있다면 건너뛰고 하나도 없다면 구별 가능하므로 답을 세준다! 소스코드123456789101112131415161718192021222324252627282930#include #include #include using namespace std; char str[1010][55];int n, m;set s; int main() { scanf(" %d %..

강호의 위치에서 갈 수 있는 건 1) +U 위로가기2) -D 아래로 가기다 1~F를 제한으로 두고 BFS를 돌리자! 소스코드1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include using namespace std;#define MAXN 1000010int F, S, G, U, D;int dist[MAXN];bool check[MAXN]; int main() { scanf(" %d %d %d %d %d", &F, &S, &G, &U, &D); queue q; q.push(S); dist[S] = 0; check[S] = true; while (!q.empty()) { int h..

수빈아와 동생의 숨바꼭질이다내가 찾아드림 수빈이는 N에 있고 동생은 K에 있다수빈이의 이동 가능한 경로는 1) N+12) N-13) N*2 그럼 이 3가지 경우를 BFS를 통해 동생을 찾으면 된다! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include #include using namespace std;int n, k;int dist[100010];bool check[100010]; int main() { scanf("%d %d", &n, &k); queue q; q.push(n); dist[n] = 0; check[n] = true; while (!q.empty()) ..

미로에서 최단거리를 구하는 문제BFS를 이용해 구할 수 있다 상하좌우 이므로 4방향 탐색을 해야한다! dist[nx][ny]를 갈 수 있는 곳이라면 dist[x][y] +1이 된다! 소스코드 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std;int arr[111][111], dist[111][111];bool check[111][111];int n, m;int dx[4] = { 0,0,1,-1 };int dy[4] = { 1,-1,0,0 }; int main() { scanf(" %d %d", &n, &m); for (int i = 0; i

DFS를 돌며 4방향 탐색을 하면 풀 수 있다! num배열에 cnt단지 수를 저장해둔다 마지막에 단지는 cnt개 있으므로 num~ (num+cnt)까지 정렬 후출력한다! 소스코드12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;bool check[30][30];int n, arr[30][30],num[1010],cnt;int dx[4] = { 0,0,-1,1 };int dy[4] = { 1,-1,0,0 }; void dfs(int x,int y) { check[x][y] = true; num[cnt]++; for (int i = 0; i

DFS와 BFS 기본문제다 제목 그대로 DFS와 BFS를 실행시키면 된다이 때 정점 번호가 작은 것을 먼저 방문하므로 정렬을 해줘야한다!c_cnt를 이용해 방문지점을 체크하는 check배열을 구별할 수 있다 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #include using namespace std;int n, m,s,check[1010],c_cnt=1;vector Graph; void dfs(int x) { check[x] = c_cnt; printf("%d ", x); for (int i = 0; i

위상정렬로 풀 수 있는 문제다장난감 n을 만드는 기본장난감 수를 다 찾으면 된다 그럼 그래프를 만들고 어떠한 장난감을 만들기 위한 장난감이 몇개인지 다 더해나가면 된다 d[i][j] => i를 만들기 위한 장난감 j의 수 여기에 다 더해나가면 d[n][k]에 n을 만들기 위한 k의수가 저장된다~! 근데 처음에 이걸 위상정렬 끝내고 밖에서 처리했는데 숫자가조금씩 차이나며 틀렸다 그래서 위상정렬 하면서 같이 처리하니까 맞더라.. ㅎ 작은 오류를 못잡은 것 같다ㅎㅎ쓸데없는 코딩은 안하는게 좋은 것 같다.짧게 간결하게 끝내야지~~! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #includ..