동적계획법2 [Swift][DP] 백준 9251번 (LCS) 요구능력 : DP 코드설명 : https://www.youtube.com/watch?v=EAXDUxVYquY 이곳에 설명을 아주 잘해주시는 교수님이 계십니다. 후기 : 여태 야매로 풀던 DP를 제대로 푸는방법을 배운것같은 강의였다. let x = readLine()!.map{String($0)} let y = readLine()!.map{String($0)} var dp = Array(repeating: Array(repeating: 0, count: y.count + 1), count: x.count + 1) for i in 1...x.count{ for j in 1...y.count{ if x[i - 1] == y[j - 1]{ dp[i][j] = dp[i - 1][j - 1] + 1 }else{ d.. 2022. 3. 10. [Swift][DP] 백준 1149번 (RGB거리) 요구능력 : DP에 대한 이해 코드설명 : 26 40 83 39 60 57 13 89 99 문제를 보면 앞뒤에 나온 컬러는 사용할 수가 없다. 우선 조건없는 점화식을 만들어보자. 조건이 없다면 최소값을 누적하는 dp이다. 그렇다면 dp[i] = dp[i - 1] + arr[i][최소가되는부분] 이 만들어진다. dp[i - 1]에는 이미 최소값이 만들어진것이라 가정한것이다. 조건을 넣은 점화식을 만들어보자. 우선 조건은 3가지가 있다. R일때, G일때, B일때. dp[i]가 R이면 이전에는 G와 B가 나와야한다. 아래 코드에서는 R이 0, G가 1, B가 2 이다. dp[i]를 R로 칠한경우의 DP가 있을것이고, G로 칠한경우의 DP가 있을것이고, B로 칠한경우의 DP가 있을것이다. 그러므로 arr배열에 .. 2021. 11. 4. 이전 1 다음