https://www.acmicpc.net/problem/1079 1079번: 마피아 첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 www.acmicpc.net 게임에서 한 명씩 지워가는 경우를 모두 고려하여 문제를 해결했다. 코드 #include #include #include using namespace std; int n; int player_num; int r[16][16]; int player; int Solve(int player_num, int night_cnt, vector cost, vector erased) { int ret = -1; ..

https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net 바깥쪽 벽에 구멍이 있을 때 물이 빠지는 것과 구멍의 높이가 낮은 게 물이 많이 빠지는 것을 고려하여 바깥쪽부터 시작하여 구멍의 높이가 낮은 것부터 인접한 방향에 구멍으로 연결되어 인접한 방향의 구역이 물이 빠지는 것을 이용하여 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, m, h; i..

https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 1번 노드가 루트인 트리를 만들고 리프 노드와 연결을 끊는 최소 비용을 구해서 문제를 해결했다. 코드 #include #include #include using namespace std; int tc; int n, m; vector adj[1001]; //(다이너마이트 수, 목적지) vector maked(1001); vector children[1001]; //(다이너마이트 수, 자식노드)..

https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 색상 트라이와 닉네임 트라이를 만들었다. 닉네임을 닉네임 트라이에 넣을 때는 닉네임을 거꾸로 해서 넣었는데, 이유는 팀명이 주어졌을 때 거꾸로 해서 닉네임이 될 수 있는 것을 빨리 찾기 위해서이다. 그래서 팀명이 주여 졌을 때 앞에서부터 색상을 찾고 뒤에서부터 닉네임을 찾아서 색상과 닉네임의 경계가 잘 맞으면 수상할 수 있는 팀으로 하여 문제를 해결했다. 코드 #include #in..

https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 각 간선이 길에 몇 번 포함되는지 개수를 구하는 방법으로 문제를 해결했다. 부모 노드와 자식 노드를 연결하는 간선은 두 정점을 모두 부모 노드 위쪽(부모 노드 포함)에서 고르는 경우를 제외하고 모두 사용되므로 전체에서 두 점을 구하는 경우((n * (n-1))/2) - 부모노드 위쪽에서 두 점을 구하는 경우(((n - sub_tree_size[there]) * (n - sub_tree_siz..

https://www.acmicpc.net/problem/2325 2325번: 개코전쟁 “앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕 www.acmicpc.net 1번부터 n번까지 최단경로를 구한 뒤 최단경로에 속하는 간선들을 저장하고 최단 경로에 속한 각각의 간선들이 없을 경우에 대한 최단경로를 구해 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, m; vector adj[1001]; vector edge; vector path; vector come_from(100..