나 요리학원 출신임

아주 쉬운 기하문제다 우선 옛날에 틀렸었는데 이유는 무조건 직사각형으로 만들어야하는데 그걸 안지켰다 근데 막상 하려니 혼자 어렵게 생각해서 직선끼리 만나고 그런경우 따지고있었다 도움을 좀 받고 보니 내가 전광판을 직사각형 모양이 나오도록 가려야만 효과가 있는걸 알았다 결국 오른쪽 왼쪽 위 아래 이렇게 가릴때만 비교하면 된다! 소스코드 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

완전탐색으로 푸는 문제다 이렇게 문제가 길면 어렵운것보다 눈에 잘 안들어와서 큰일이다 계속 다 풀어놓고 변수명 틀리고 0,1 틀리고 실수가 많다! 집중해서 한번에 확 푸는 연습좀 해야겠다 이 문제는 톱니바퀴를 직접 굴릴 필요는 없고 그냥 2,6번째를 r,l 이라는 화살표로 본다고 생각하고 화살표를 움직이면 된다! 그럼 마지막에 화살표가 움직인 거리만큼 0에서 움직여보면 된다 소스코드 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 56 57 58 59 #include #incl..

숨바꼭질? 그 문제랑 비슷한 문제다 내가 갈 수 있는 경우를 다 큐에 넣고 bfs를 돌리면 된다 이 때 시간마다 칸이 사라지므로 그 경우를 큐의 사이즈를 통해 해결하자! 평소처럼 큐가 비어있으면 돌리는게 아닌 현재 시간에 갈 수 있는 만큼만 큐를 돌리는거다 현재 시간에 움직일 수 있는 칸 == 현재 큐 사이즈 이용 ㄱㄱ 문제를 잘 읽어보면 N번 칸 보다 더 큰 칸으로 간다면 1이므로 조건을 잘 확인하자! 소스코드 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 56 57 58 ..

dp 문제다 테이블을 잡을 때 d[n][k]로 잡았다 숫자 n을 만들 때 마지막 수가 k인 경우의 수다 그럼 이 테이블을 사용해서 계속 채워나갈 수 있다 중복이 없다고했으니 우리는 정렬했다고 가정하고 마지막수가 가장 큰 수라고 생각하자 그럼 마지막 수가 1,2,3 오는 경우를 생각하면 d[n][2] = d[n-2][1~2]가 된다 왜냐면 마지막에 오는 가장 큰 수는 2이므로 1부터 2까지 보는것이다 아래부터 축적해나가면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int n; int d[10010][4]; int main() { scanf(" %d", &n); d[1][..