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

www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙하가 2차원 배열로 주어지는데 빙하 상하좌우에 0이 있다면 빙하가 0 하나당 -1씩 줄어든다. 구현하면서 신경 쓸만한 부분은 날짜가 지남에 따라 빙하가 녹는 것, 빙하로 이루는 땅이 2개 이상인지 확인할 것 2개만 신경써주면 된다. if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--; else if (!vis[nx][ny]) { q.push({ n..