DMLab 알고리즘 스터디 9주차

개요

9주차 스터디는 dp 관련 4문제였다.

A번

14494

문제 요약

오른쪽, 아래, 오른쪽 아래 대각선으로만 이동해서 (1, 1)부터 (n, m)으로 이동하는 경우의 수 구하기

설명

dp[y][x] = dp[y-1][x] + dp[y][x-1] + dp[y-1][x-1]

B번

10164

문제 요약

격자에서 (1, 1)부터 (n, m)으로 이동하는데, k번째 칸을 반드시 지나야 한다. 이때 이동하는 경우의 수 구하기

설명

dp[y][x] = dp[y-1][x] + dp[y][x-1]
저걸 두번 계산해 곱해주면 된다.

C번

5582

문제 요약

두 문자열에서 연속 부분 문자열이 겹치는 최대 길이 구하기

설명

A[y]와 B[x]의 문자가 같을 때,
dp[y][x] = dp[y-1][x-1] + 1
그 과정에서 최댓값을 구하면 된다.

D번

1086

문제 요약

집합의 순열 중 K로 나누어 떨어지는 수의 개수 구하기

설명

풀지 못했다.

후기

한 문제를 못 풀어서 아쉬웠다. 다음에 업솔빙 해야겠다.