동적 계획법을 이용하면 풀기 편하다.
d[마을수][지난날수]로 자료형을 잡고
if(connected[현위치][마을])
d[현위치][날짜] += d[마을][날짜-1]/deg[마을]로
구할 수 있다.
그런데 제출하면 왜 틀리다고 나오는지 모르겠다;
책에있는데로 그대로 따라하는데...
알고스팟 뭔가 좀 이상하다.... 물론 나한테 문제가 있는거지만 ㅠ
728x90
알고리즘 문제들은 서로 다른 문제 같아도 같은 개념을 사용하고 있음을 이해하면
문제풀기가 편하다.
줄세우기문제는 앞으로 옮기고 뒤로 옮기고 해서 어려워 보이지
사실은 증가하는 순열중 가장 긴 순열을 찾으라는 문제와 같다.
옮기는 횟수는 전체 배열의 크기에서 증가하는 순열중 가장 긴 순열의 개수를 뺀 것과 같다.
아.. 이렇게 빠르게 이해됫으면 얼마나 좋을까
728x90
세개의 문자에 대해서 LCS를 찾는것
d[][][] 3차원배열을 만들고 점화식은 같다
사실 공간에 취약해서 왜 이렇게 답이되는지 증명하라면 좀 시간 걸릴것 같다
하지만 LCS 문제를 푸는데 착안해서 풀었다.
728x90
LCS 살짝 변형한 문제다
문자열에대한 dp[][]배열을 만들어주면 된다.
728x90
LCS문제
모두의 부부수열이 되는 수열중 가장긴것을 찾는문제
전형적인 dp문제인데 이때 d배열을 2차원으로 해야한다는 점이 중요
점화식만 잘 만들면 어렵지 않게 해결 할 수 있다.
현재 위치의 dp값을 지정해주려면
if(A[i] == B[i]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])
else dp[i][j] = max(dp[i][j-1], dp[i-1][j])
요렇게
728x90
