www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 탐색 + 구현 문제였다. 고슴도치는 물이 들어올 곳에 갈 수 없다는 말에 처음에는 bfs 한 번에서 고슴도치와 물을 전부 pop 해가면서 했는데 그러한 접근은 while문이 한번 돌 때마다 하나씩 pop 되기 때문에 실패했다. 다시 생각해봤는데 물의 위치에서 BFS한 것과 고슴도치 위치에서 BFS 한 것을 통해서 고슴도치가 갈 위치 + 1 < 물이 들어올 위치값 을 만족한다면 고슴도치가 갈 수 있겠다는 생각이 들어서..

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/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 간단한 DP 문제였다. 삼각형이 n = 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 이런 식으로 주어진다면 가장 밑 줄에서 가장 큰 수를 얻으려면 0번째 줄에서 그다음 줄로 현재 값에서 왼쪽으로 내려가던가, 오른쪽으로 내려가던가 이 두 가지 경우의 수만 따져주면 된다. max(solve(x + 1, y + 1), solve(x + 1, y)) + ar[x][y] table[x][y] 의 값은 결국 위의 식처럼 될 것이다. #include #include #include ..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구의 관계가 주어진다. 예제를 보면 Fred Barney Betty Wilma Barney Betty 가 주어지는데 Fred - Barney 가 연결되었으니 총 2명 Betty - Wilma 가 연결되었으니 총 2명 Barney - Betty 인데 Betty - Wilma, Barney - Fred 가 서로 친구이니 총 4명 즉, 집합이 주어지는데 같은 부모 노드 같은 구성원이 존재한다면 Union..

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 도시의 수가 주어지고 인접 행렬이 반사 행렬로 주어지니 무향 그래프로 봐도 된다. 이후 여행 갈 도시의 동선이 주어지는데 이를 path 배열로 받아줬다. 처음에는 DFS로 접근해서 void DFS(int cur) { vis[cur] = true; for (int i = 1; i j를 union 해준다 이후 path 배열을 입력받고 path[0] 의 루트 노드를 찾는다 path 배열을 돌면서 path[0] 의 루..

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터를 활용해서 푸는 문제였다. 문제를 이해하는데 어려운 부분은 없었는데 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이 나는 저 S 이상이 아니라 정확히 S가 되는 것만 카운팅 되는 줄 알고 30분을 소비했다... #include #include using namespace std; int ar[100001], n, m, s, e, sum, a..