전체 글 썸네일형 리스트형 SPOJ)BATMAN2 문제:http://www.spoj.com/problems/BAT2/ 각 방의 가중치가 주어지고 두명의 사람이 이동을 한다. 한 사람은 1에서 부터 다른 한사람은 N에서 부터 이동할 때 겹치지 않는 경로로 가중치가 증가하는 순서대로 이동할 때 밟을 수 있는 방의 수의 최댓값을 출력하는 문제이다. 다이나믹 프로그래밍을 이용하여 dp[pos][x][y]의 정의를 1번부터 pos번 정점까지 확인 했을 때 한 사람은 x번 정점을 마지막으로 한사람은 y번 정점을 마지막으로 밟았다고 생각하면 점화식을 세울 수 있다. dp[pos][x][y]= max(dp[pos][a[pos]][y]+1, dp[pos][x][a[pos]]+1 , dp[pos][x][y]) 1234567891011121314151617181920212.. 더보기 UVaOJ)12460 Careful teacher 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3891 문제를 간략하게 설명하면 사전에 존재하는 단어들이 주어진 뒤 쿼리가 들어올 때 쿼리에서 들어오는 두 단어를 A와 B라고할 때 A를 B로 바꿀 수 있는지 여부를 물어보는 문제이다. 이 때 A를 B로 바꾸는 경우는 한글자 씩 바꿀 수 있으며 단, 한글자를 바꾼 단어도 사전에 존재하여야만 바꿀 수 있다. 이 문제는 사전에 존재하는 단어들을 정점으로 생각하고 1글자 다른 단어들을 간선으로 묶어주면 A와 B가 같은 컴포넌트에 존재하는지 여부를 묻는 문제로 변형된다. 이는 disjoint-set을 통하여 해결해줄 수 있다. N제한이 20000이지만 시간.. 더보기 BOJ)12922 블럭 퍼즐 문제: icpc.me/12922 1x1x2 블럭이 정사각형 그리드에서 이동할 때 게임승리를 불가능하게 뚫어야하는 구멍의 수를 출력하는 문제이다. 문제에서 블럭의 이동경로를 살펴보면 시작점에서 부터 4방향으로 3칸 떨어진 지점에만 서있을 수 있다. 이를 이용하여 모든 정점에서 3칸 떨어진 지점으로 그래프를 구성해주는데 이 때 간선의 capacity는 지나가는 경로에 뚫어야하는 구멍 수가 되야되고 해당 정점에 구멍을 뚫는 경우는 정점을 분할하여 사이에 capacity를 1로 주는걸로 그래프를 모델링 해주면 src에서 sink로의 mincut을 구해주면 답을 구해낼 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 더보기 이전 1 ··· 31 32 33 34 35 36 37 ··· 118 다음