나 요리학원 출신임

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..

수를 1X2 or 2X1 크기의 블럭으로 묶고 , 묶인 수들의 차의 합의 최대 / 최소를 찾는문제다 비트dp를 이용해서 풀 수 있다!테이블은 d[위치][상태] 이다 -> 여기서 상태는 (위치~위치+3)까지의 상태0부터 마지막 칸까지 가며 상태를 보고 내가 할 수 있는 행동들을 하면 된다내 위치에서의 상태는 2가지다 1) 내가 있는 칸이 안채워진 경우여기서 x,y를 보고 또 판단 해야 한다n번째 줄이 아니라면 세로 가능~!2번째 칸이 아니고 옆칸이 비었으면 가로 가능~! a) 가로로 놓을 수 있는 경우 (내 옆칸도 비었을 때)b) 세로로 놓을 수 있는 경우 (위에서부터 보며 내려오므로 무조건 가능) 2) 채워진 경우이 때는 바로 다음 블럭으로 넘어간다 (pos+1,(state>>1)) 이렇게 최대 , 최소..

처음봤을 때 DP로 풀다가 실패해서 안푼 문제다그러다가 오늘 다시 다익스트라로 풀었다 다익스트라로 생각하면 쉽게 풀 수 있다내가 K번 말처럼 뛸 수 있으므로 cnt =K로 하고 cnt를 저장해서 가져다니면 된다 pq에 넣고 다니면 끝이다..!아 근데 이문제 가로 세로 잘봐야한다 ㅋㅋㅋ 그리고 다들 오타가 안나도록 조심.. n,m,= 이런거... 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include #include #include #include using namespace std;int..

옛날에 틀린 DP 문제다지금보니 점화식은 맞았는데 정렬은 안해서 틀렸다 아이템을 다 먹는 경우의 수 이므로 현재아이템-> 다음아이템 의 경우의 수를모두 곱하면 답이된다! 그래서 벡터에 아이템 좌표를 다 넣고 정렬을 한 후 dp를 하면된다~~! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #include #include using namespace std;int d[111][111], arr[111][111];int n, m, a, b; int go(int x1, int y1, int x2, int y2) { if (x1>x2 || y1>y2) return 0;..