백준

문제https://www.acmicpc.net/problem/2293 입력n = 동전의 종류 (1~100)k = 목표 금액 (1~10,000)coins = 각 동전 금액결과ans: Int = k 목표 금액을 만들 수 있는 경우의 수해석dp를 통한 경우의 수를 카운팅하는 문제 느낌이다. dp 배열의 규칙은 다음과 같다. dp[i] = i원을 만들 수 있는 경우의 수   dp 배열을 저렇게 잡으면 점화식은 이렇게 따오를 것 같다 C를 만들기 위해 B는 동전 A가 부족한 상황이면dp[c] = dp[b] + dp[a] 상황이다.코드import Foundationlet nk = readLine()!.components(separatedBy: " ").map{Int($0)!}let (n,k) = (nk[0], nk..

문제https://www.acmicpc.net/problem/9251입력s1 = 문자열s2 = 문자열최대 1000글자결과ans: Int = 가장 긴 부분 수열의 길이해석LCS((Longest Common Subsequence))이므로 dp가 가장 먼저 생각난다. 점화식dp[n][m] = s1의 n번째 s2[m]번째 문자까지 가장 긴 부분 수열의 길이(if \ s[i] == s[j]),  (dp[i][j] = dp[i-1][j-1] +1 )  ,같은 문자를 찾으면 바로 직전 최장 부분 수열 + 1 (else) (dp[i][j] = max(dp[i-1][j], dp[i][j-1]) ,같은 문자가 없을 경우 이전 경우의 수에서 가장 긴 것을 저장 S1 = ACAYKP, S2 = CAPCAK 일 경우 dp 배열..