Longest Increment Subsequence 오늘 추가로 풀어본 알고리즘 문제는 최장 증가 수열이다. 예젠에도 백준에서 매우 유사한 문제를 풀어봤었다. DP 문제를 빠르게 푸는 방법은 정확한 의미의 점화식을 세우는 것이다. 처음 문제를 풀 때 세웠던 점화식은 i 번째 원소를 시작점로 하면서 j 번째 원소를 끝점으로 하는 최장 증가 수열의 길이라고 정의하고 풀려고 노력해 보았다. 잘못된 점화식을 세웠을 때 가장 빠르게 알 수 있는 문제가 i - 1 또는 j -1 과 현재 dp[i][j]와의 관계를 찾는 것이 불가능하거나 가능하더라도 매우 복잡해진다. 따라서 구글 검색을 통해 내가 생각한 점화식이 틀린지 확인해 보았는데, 역시나 틀린 점화식이었다. 알맞은 점화식은 dp[k], k 번째 원소를 끝으로 하는 최장 증가 수열의 길이이다. 배열 dp는 1로 .. DP 문제 Number of dice rolls with target 주사위 면의 수 f인 (1...f) d 개의 주사위를 굴려 target을 만드는 경우의 수를 구하시오. 문제 및 예제의 원본이다. 문제를 딱 보고 든 풀 수 있는 방법 중 하나는 DFS, BFS 였다. 하지만 DFS, BFS로 하면 30면 짜리 주사위의 30개를 굴려서 특정 target이 될 수 있는 경우의 수를 구할 때 시간초과(TLE)가 날 수 있다. 그렇다면 다른 방법으로 풀 수 있는 게 무엇일까 생각해봤다. DP 방법의 풀이가 가능한 지 알아보자. 일단 2차식 형태의 점화식을 세워보자. (여기서 2차식이라 함은 이차원 배열을 사용한다고 생각하면 된다.) dp[d][k]를 주사위 d개로 t를 만들 수 있는 경우의 수라고 하자. (항상 dp에서는 점화식을 어떻게 정의하느냐가 중요하다.) dp[d][t.. 이전 1 다음
