문제https://www.acmicpc.net/problem/15486 입력n: Int = 남은 근무 일 t: [Int] = 근무 시간p: [Int] = 일급1 결과ans: Int = 퇴사할 때 최대 수익해석점화식은 문제에서 금방 구할 수 있다.dp[i] = i 날까지 왔을 때 최대 수익 j = i + t[i] = 다시 일을 할 수 있는 날 , i = 1이고, t[i] = 1이면 , 다음일은 2일부터 바로 시작할 수 있다. 하지만 여기서 중요한 점은 일을 많이한다고 수익이 최대가 아니다.  그러므로 현재 i날을 기준으로 전날 까지의 최댓값을 계속 가져가야한다. 코드import Foundationvar t: [Int] = [0]var p: [Int] = [0]let n = Int(readLine()!)!f..

문제https://www.acmicpc.net/problem/11722입력n: Int = 수열의 길이arr: [Int] = 수열 1 결과ans: Int = 가장 긴 감소하는 부분 수열 길이해석LIS의 형태로 간단한 점화식을 세울 수 있다. dp[i] = i 전까지 가장 긴 감소하는 부분 수열 길이 반복문 한개는 i = 현재 값 , 나머지 반복문 j = i 직전까지총 최대 1000 x 1000을 돌며  arr[j] > arr[i] 일 때 dp 배열을 갱신한다. 코드import Foundationlet n = Int(readLine()!)!let arr = [-1] + readLine()!.components(separatedBy: " ").map{Int($0)!} var dp: [Int] = [Int](r..

문제https://www.acmicpc.net/problem/1520 입력n, m = 지도의 행 , 열 길이 arr: [[Int]] = 각 지점의 높이결과ans: Int = 이동 가능한 총 경로 수해석내리막길인지 판별한후 dfs를 통해 목적지에 도달 후 return을 통해 카운팅을 해주자.  코드import Foundationlet nm = readLine()!.components(separatedBy: " ").map{Int($0)!}let (n,m) = (nm[0], nm[1])var arr: [[Int]] = []for _ in 0.. Int { if x == n-1 && y == m-1 { cache[x][y] = 1 return 1 } if..

문제https://www.acmicpc.net/problem/2294 입력n = 동전의 종류 (1~100)k = 목표 금액 (1~10,000)coins = 각 동전 금액결과ans = k금액을 만들기위해 사용한 동전의 최소 개수. 불가능한 경우에는 -1해석이전에 풀었던 동전1 문제를 최소 개수 구하는 점화식으로 바꾸면 끝dp[i] = i 금액을 만들기위해 사용한 최소 개수 코드import Foundationlet nk = readLine()!.components(separatedBy: " ").map{Int($0)!}let (n, k) = (nk[0], nk[1])var coins: [Int] = []for _ in 0.. k { continue } for i in 0...k-coin { ..

문제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 배열..