2017/06/17 썸네일형 리스트형 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이지만 시간.. 더보기 이전 1 다음