목록전체 글 (51)
PS 부수기
dp[index][heightDif] = index번째 블록부터 사용했을 때(사용을 고려했을 때), 그리고 현재 두 탑의 높이차이가 heightDif일 때 미래에 세워질 두 탑의 높이 중 높은 높이의 최댓값이다. 우리가 구하려하는 답은 dp[0][0]임을 알 수 있다. Case 1 : index번째 블록을 사용하지 않는다. -> 변한건 없이 바로 dfs(index+1, heightDif)를 호출 Case 2 : index번째 블록을 더 높은 탑에 쌓는다. -> heightDif는 a[index]만큼 더 늘어날 것이다. 그리고 탑의 최대 높이도 a[index]만큼 늘어날 것이다. Case 3 : index번째 블록을 더 낮은 탑에 쌓는다. -> heightDif는 a[index]-heightDif의 절댓값..
자주 쓰게 될 코드같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 vector fact; llong add(llong a, llong b) { a += b; if (a >= MOD) a -= MOD; return a; } llong sub(llong a, llong b) { a -= b; if (a > n >> k; fact = vector(n+1); fact[0] = 1; for (int i = 1; i
우선 dp를 돌기 전에 isPal 이차원 배열을 만들어 놓고, L번째 index와 R번째 index 사이의 string이 palindrome이 맞으면 1, 아니면 0을 저장한다. 그리고 dp[index] = index에서 시작하여 string 끝까지 만들 수 있는 최소 팰린드롬 분할 갯수라고 정의하자. 즉 우리가 알고싶은 답은 dp[0]의 값이다. i를 index~string 끝까지 돌렸을 떄 isPal[index][i]가 1이라면, index~i까지는 palindrome이라고 할 수 있고, 그 뒤에 남은 string에 대해 최솟값을 구해주는 식으로 짜면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30..