www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 끔찍한 구현 문제였다. 어떻게 구현해야 할지 생각이 안 나서 다른 풀이를 참고했는데 pair 객체를 통해 정렬해주면 쉽게 풀리는데 잘 익혀둬야겠다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가..

www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net (1, 1)에서 (n, m)으로 가야 하는데 오른쪽, 밑, 오른쪽 밑으로 가면서 가져갈 수 있는 가치 중 최댓값을 구하면 된다. 우선 오른쪽 밑 대각선으로 가는 부분은 없다고 생각해도 된다. 왜나면 '무조건' 위나 왼쪽에서 챙겨가는 것이 더 이득이기 때문이다. 따라서 그냥 2차원 누적 합으로 생각해도 된다. #include #include using namespace std; int n, m, x..

www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 백준 대회가 있길래 참여해서 풀어봤는데 테스트 케이스 2개만 맞추고 나머진 실패했다.. 이후에 참고해서 다시 풀어봤는데 조건처리 부분에서 미숙한 부분 때문에 실패한 것 같다. #include #include using namespace std; int n, m, r, x, y, ans; char dir; int ar[105][105], status[105][105]; void f(int x, in..

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제에서 가중치는 주어지지 않는다. 따라서 우리가 직접 가중치값을 설정해줘야 하는데 각 별의 위치를 받으면 \(O(N^2)\)으로 가중치를 쉽게 설정해줄 수 있다. 거리 공식은 \(\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\) 이다. #include #include #include #include using namespace std; struct P { int u, v; double w; }; v..

www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이산수학에서 최소 스패닝 트리를 구하는 방법에 대해 공부하길래 이왕 하는 겸 알고리즘으로 풀어보고 싶어서 구현해봤다. 처음에는 프림 알고리즘 먼저 구현해보려 했는데 유니온 파인드도 복습할 겸 해서 크루스칼로 풀었다. int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; p[y] = x; return true..

www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 컴퓨터 a가 b를 의존한다면 b컴퓨터가 감염되었을 경우 c초 뒤에 a컴퓨터도 감염된다. 결국 모든 노드에서 한 방향으로 가는 최단거리를 안다면 쉽게 풀리는 문제였다. 첫 시작점에서 다익스트라를 쓰고 INF가 아닌 노드들을 카운트해주고 그 거리 값 중에서 가장 긴 거리 값이 정답이 된다. #include #include #include #include using namespace std; const int INF =..