본문 바로가기

분류 전체보기

BOJ)2275 트리의 높이 줄이기 문제: icpc.me/2275 트리에서 모든 리프까지의 거리가 H이하로 되게 만들 때 비용의 최솟값을 구하는 문제이다. 우리는 가능하다면 부모에서 높이를 줄여야지 한번에 여러 리프들의 높이를 동시에 줄이는게 가능하다는 사실을 이용하여 모든 리프에 줄여야할 가중치를 할당하고 바텀업 방식으로 부모에서 높이를 줄이는게 가능하다면 줄이는 방식으로 문제를 해결해주면 된다. 문제를 해결하기 위하여 dfs로 전처리를 해줘야하는데 해당 노드의 깊이 중첩 가중치를 미리 구해주면 쉽게 계산해 줄 수 있다. 아래 코드에서 각 배열이 의미하는건 r[v]는 v노드에서 줄여야하는 가중치이고 d[v]는 v까지의 누적 가중치이다. 123456789101112131415161718192021222324252627282930313233.. 더보기
BOJ)8012 한동이는 영업사원! 문제:icpc.me/8012 한동이가 방문해야 할 도시를 x->y->z->w 순이라면 x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다. 결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다. x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#in.. 더보기
BOJ)1761 정점들의 거리 문제:icpc.me/1761 두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다. 우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다. 하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다. 우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다. lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면 두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다. 이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다. 12345678910111213141516171819202122232425262728293031.. 더보기
BOJ)2512 예산 문제:icpc.me/2512 최소중의 최대를 구하는 전형적인 파라메트릭 서치 문제이다. 다만 주의해야 할 건 모든 인풋 a[i]의 합이 m보다 작을 경우 a[i]중에 최댓값을 출력해줘야 하는 예외 케이스가 있다. 123456789101112131415161718192021222324252627282930313233343536#include #include typedef long long ll;using namespace std;ll n, a[10000], m, lo, hi, ma, s;int main() { scanf("%lld", &n); for (int i = 0; i = s) { printf("%lld\n", ma); return 0; } lo = 0; hi = 21000000000; while (.. 더보기
BOJ)1576 DNA점수 문제: icpc.me/1576 점수판을 채우는 규칙이 주어질 때 주어진 DNA 문자열의 각 문자열에서 얻을 수 있는 점수의 평균의 최댓값을 구하는 문제이다. 우리는 평균의 최댓값을 구하기 위해서 총점의 최댓값을 구하면 된다. 결국 총점이 최대가 되도록 점수판을 채우면 되는것이다. 우리는 다이나믹 프로그래밍을 이용해서 총점이 최대가 되도록 점수판을 채워나갈 것이다. 점수판을 채우는 순서는 임의로 지정해 줄 수 있다. dp테이블은 dp[4][4][10*16*2] 이 될것이다. dp 테이블이 의미하는 바는 dp[x][y][z]일때 (x,y)까지 채웠고 점수판의 점수 총합이 z일 때 총점의 최댓값으로 정의하면 된다. 우리는 점수판의 총점이 음수가 될 때도 있으니 그걸 고려하여 10*16의 총점에 2를 곱해주었다.. 더보기
BOJ)10265 MT 문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이.. 더보기
BOJ)3977 축구 전술 문제: icpc.me/3977 A->B로 이동해야하는 전술들이 주어질 때 시작 지점이 될 수 있는 위치를 찾는 문제이다. 이 때 적절한 시작지점이 없으면 Confused를 출력하면 된다. 여기서 SCC를 이루는 그룹이면 어떤 곳에서 시작하던 topology에 의해 나머지 지점들을 전부 탐색 가능하니 정점들을 SCC로 묶은 뒤 indegree가 0인 지점이 하나일 때는 해당 SCC에 속하는 모든 점들이 시작지점이 될 수 있고, 만약 indegree가 0인 지점이 여러곳일 경우에는 어떤 지점에서 시작해도 모든 점을 방문 불가능하기 때문에 Confused를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기
BOJ)4196 도미노 문제:icpc.me/4196 X번 블록이 넘어지면 Y번 블록이 넘어지는 정보가 여러개 주어질 때 도미노를 직접 넘어뜨려야하는 최소 블록 개수를 출력하는 문제이다. 도미노를 직접 넘어뜨려야 한다는 건 결국 다른 도미노에 의해서 넘어지지 않는다는걸 의미하는데 이는 곧 indegree가 0인 정점의 개수다. 또 하나 고려해줘야 하는 경우가 있는데 cycle을 이룰 경우 indegree가 0이지 않지만 누가 먼저 넘어지지 않는 이상 영원히 넘어지지 않는다. 따라서 우리는 방향 그래프에서 SCC를 구해준 후 SCC로 이루어진 그래프에서 indegree가 0인 SCC의 개수를 세어주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839.. 더보기
BOJ)3665 최종 순위 문제:icpc.me/3665 작년의 등수가 주어지고 올해 등수가 역전 된 두 팀의 목록이 주어질 때 올해 순위를 발표하는 문제이다. 우선 작년의 등수를 기반으로 n^2의 방법으로 간선을 연결해주고 올해에 뒤 바뀐 순위를 기반으로 간선의 방향을 바꿔준다. 이후 위상정렬을 해주면 되는데 이 때 큐에 동시에 2개가 들어간다면 ?를 출력하고 n번을 돌리기전에 큐가 비어버린다면 사이클이 생긴것이므로 IMPOSSIBLE을 출력 해 주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #.. 더보기
BOJ)2637 장난감조립 문제:icpc.me/2637 장난감 완제품 N을 만드는데 필요한 기본 부품의 종류와 수를 출력하는 문제이다. 여기 기본 부품은 indegree의 수가 0인 정점들이 되고 위상정렬 순서대로 부품의 개수를 중첩 시켜 나가면 답을 구할 수 있다. a[x][y]가 의미하는건 x번 부품(제품)을 만드는데 필요한 기본 부품 y의 개수이다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;int n, m, a[101][101], in[101], x, y, z;vector vt;int main() { scanf("%d%d", &n, &m); vt.. 더보기

티스토리툴바