나 요리학원 출신임

구현하는 문제다 문제 이해를 잘못해서 한시간넘게 틀리고 난리를 쳤다 문제를 자세히 보면 거리가 d이하인 적 중에 가깝고 가장 왼쪽에있는 적이 우선순위가 높다 아마 틀리는 사람들 대부분이 이 조건을 제대로 이해 못해서 틀리겠지...! 함수별로 기능을 살펴보자 inner() => 간단하게 범위를 넘어가는지 파악하는 함수 dist() => (x,y) , (a,b) 의 거리를 구해주는 함수 attack() => 공격할 적을 고르는 함수다 가장 헷갈리는 부분이였다 내가 공격할 적을 거리기준,행기준,열기준으로 for문을 잡았다 거리가 가까운 적들 중 왼쪽행에있는 적들을 봐준다 만약 조건을 만족하는 적을 찾으면 vt에 넣고 끝! solve() => 궁수 3명을 두고 적들을 총 몇명 죽이는지 계산해주는 함수다 적들이 ..

숫자 사이의 사이클을 찾는 쉬운 문제다! 스택 개념을 사용하면 금방 풀 수 있다 진짜 스택을 써도 괜찮고 배열에 넣어도 괜찮다 먼저 숫자를 계산하고 check배열을 통해 표시해준다 그리고 스택에 계속 넣어준다 그러다가 만약 이미 나온 숫자가 또 나온다면 스택에서 그 숫자부터 top까지의 수가 답이된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include #include #include using namespace std; bool arr[1000010]; int n, k; int getnum(int num) { return((n*num) % k); } int main..

bfs + union_find를 배우고 풀면서 이 문제를 풀어봤다 각 칸들을 하나의 집합이라보고 문명을 bfs를 통해 넓혀가면서 4방향으로 합쳐주면 된다 합치면서 0이였던 칸은 1로 바꿔주며 큐에 넣어준다 문명이 커지다가 문명끼리 인접해도 합쳐지기 때문에 한번씩 더 봐줬다 근데 문제는 마지막에 다 합쳐졌는지 확인하는 과정에서 완탐을 버리지못하고 하나하나 다 확인해줬다~~! 시간이 덕분에 쭉~쭉 증가했다 내일 이것좀 수정해봐야겠다 추가로 이분탐색+bfs를 통해서도 많이 해결하던데 한번 공부해봐야겠다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..

아주 쉬운 기하문제다 우선 옛날에 틀렸었는데 이유는 무조건 직사각형으로 만들어야하는데 그걸 안지켰다 근데 막상 하려니 혼자 어렵게 생각해서 직선끼리 만나고 그런경우 따지고있었다 도움을 좀 받고 보니 내가 전광판을 직사각형 모양이 나오도록 가려야만 효과가 있는걸 알았다 결국 오른쪽 왼쪽 위 아래 이렇게 가릴때만 비교하면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int x1,x2,x3,x4,y1,y2,y3,y4; int main(){ scanf(" %d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); if(y3

유니온 파인드를 이용하는 기본문제다 친구면 비용이 작은 사람들에게 합쳐준다! 마지막으로 내가 0이라고 생각하고 1~n까지 merge해주면서 비용을 합쳐주면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include using namespace std; int n, m, k; int arr[10010]; int p[10010]; int find(int x) { if (p[x] == x) return x; return p[x] = find(p[x]); } void merge(int x, int y) { x = find(x); y..

옛날에 이상하게 풀고 틀렸던 문제다 오늘 다시보니 다익스트라가 먼저 떠올라서 풀었다 N의 크기가 작아서 덕분에 풀었다 다익스트라를 모든 소에서 돌리면서 다리가 있다면 비용을 1 없다면 0으로 탐색하면된다 그리고 소의 위치를 돌며 가는데 비용이 든다면 set에 저장해주자 그럼 set의 사이즈가 정답이 된다! 풀고나서 사람들을보니 다들 시간도 메모리도 적게쓰고 bfs 혹은 유니온파인드로 풀었다 유니온파인드 공부 부수러가야겠다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55..

BFS를 이용해 풀 수 있는 문제다 2년전에 풀다가 직접 누구나 풀 수있는 방법인 매번 bfs하고 얼음녹이기를 했다가 시간초과나서 틀렸었다 ㅎㅎ 시간을 어떻게 줄일까 고민하다가 실패했는데 오늘 질문을 보다가 얼음을 매번녹이지말고 다음에 녹을것을 큐에 넣으라는 말을 봤다 그제서야 떠올랐다..!! 이런 생각은 어케하는걸까 문제를 푸는 방법은 bfs를 2개 돌린다고 생각하면 된다 백조 1마리가 도는 bfs와 땅(== '.') 이 도는 bfs 먼저 백조가 갈 수 있는 땅은 모두 다 가야한다 그리고 녹아야 할 땅을 bfs를 통해 모두 녹여준다 이걸 반복하는데 백조가 갈 수 있는 땅에 인접한 얼어있는 땅은 백조 bfs에서 check를 true로 바꿔주고 얼음 bfs에서 큐에 넣어준다 이 작업이 백조가 다음날부터 갈..

완전탐색 문제만 주구장창 풀고있다 6방향 탐색으로 풀라는게 뻔히 보이지만 계속 답이 안나왔다 x,y,z를 거꾸로 저장하고 다르게 입력하고 힘이들었다.. 코드가 복잡해질수록 잘 안보이니까 함수화를 좀 시켜야겠다 먼저 이 문제는 bfs+순열+조합으로 알고있다면 풀 수 있다 각 층을 정하는 방법은 순열을 사용해야한다 => 5! 그리고 몇바퀴 회전을 돌리지는 조합으로 정해야한다 4^5 마지막으로 (0,0,0) -> (4,4,4)의 최단거리를 찾아야한다 => bfs 바퀴수는 cnt에 담고 0,1,2,3 바퀴만큼 돌려줬다 그리고 나머지는 집중해서 확실하게 코딩하기가 전부다..! 순열은 next_permutation을 사용했고 조합은 5중 for문과 백트래킹으로해봤는데 시간이 20ms차이밖에 안난다 층을 정할때는 o..

그리디로 푸는 너무 쉬운 문제인 줄 알고 한대맞은 문제다 A형 기출 문제니까 보기 쉽게 함수를 좀 많이 짜놨따 먼저 푸는 방법을 생각해보자 1. (0,0) ->(10,10) 까지 한칸씩 차례로 본다 2. 내 현재 위치의 값이 0이라면 => 다음칸으로 간다 3. 내 현재 위치가 1이라면 3-1) 종이로 덮어야하므로 종이가 몇개남았는지본다 3-2) 이 때 모든 경우 다 보니까 최대한 빠르게 큰 것부터 덮어보자 3-3) 해당 종이가 아직 남아있다면 can_cover를 통해 덮을 수 있는지 확인 3-4) 덮을 수 있으면 현재 종이로 덮는 위치를 임시변수에 저장시키고 3-5) 종이로 덮은 후 (pos+1,cnt+1)로 다음칸으로 덮은 종이 수를 올리고 떠나자 3-6) 끝난 후에는 다시 원래대로 돌려준다 4. 모든..

완전탐색을 이용해 부분집합을 만들어보면 된다 비트를 이용해보자 편하게! 0~(1