www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net board에 2개의 돌을 놓을 수 있는 경우를 모두 확인해서 상대의 돌이 가장 많이 죽는 경우를 구했다. 상대의 돌은 그룹별로 묶어서 저장을 하고, 2개의 돌을 놓았을 때 없어지는 그룹들을 확인해 그 그룹들의 돌의 개수를 세서 총 죽는 돌의 개수를 구했다. 코드 #include #include #include #include using namespace std; int..

www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net 섬을 발견했을 때 해당 섬에 속한 땅을 모두 체크해서 같은 섬을 중복으로 세지 않고 섬의 개수를 구했다. 코드 #include #include #include using namespace std; int w, h; int board[50][50]; int check[50][50]; int dxdy[8][2] = { {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,..

www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) �� www.acmicpc.net 트리에서 다이나믹 프로그래밍(트리DP)를 통해 문제를 해결했다. 루트의 번호가 r인 트리를 만들고, 트리의 정점의 수를 구하면서 cache에 각 노드가 루트인 서브 트리의 정점의 개수를 저장했다. 코드 #include #include #include using namespace std; vector adj[100001]; vector maked..

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망�� www.acmicpc.net 트리에서 다이나믹 프로그래밍 (트리DP?)를 이용해서 문제를 해결했다. 트리를 생성해서 루트 노드가 얼리아답터인 경우와 그렇지 않은 경우 중 트리의 얼리 아답터의 수가 더 적은 값을 출력한다. cache를 사용해 어떤 노드가 얼리아답터일때와 얼리아답터가 아닐 때 계산한 값을 저장해 중복된 계산을 피했다. 부모 노드가 얼리 아답터가 아니라면 자식 노드는 무조건 얼리아답터이지만, 부모 노드가 얼리 아답터인..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net there로 이동할 때 지금 이동하는 depth가 기존 there의 depth보다 더 작을 경우에만 이동하면서 탐색을 진행했다. 코드 #include #include #include using namespace std; int depth[100001]; void Pre() { for (int i = 0; i < 100001; i++) depth[i] = 987654321;..

www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net bfs를 통해 start에서 dest로 가는 가장 빠른 시간을 구하는데, 가장 빠른 시간으로 가는 방법의 수도 구해야 되므로, there로 이동할 때 there가 발견된 적이 있어도 depth[here] + 1 == depth[there]이면 이동할 수 있도록 했다. 코드 #include #include #include using namespace std; int dis..