DP29 [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. [Swift][DP] 백준 15988번 (1, 2, 3더하기 3) 요구능력 : DP에 대한 이해 코드설명 : 문제를 설명해주면 1과 2와 3중 한개 이상을 더해서 주어진 수를 만드는 문제이다. 처음 접해보시는 분들은 어렵게 느껴질 수도 있는데, 이 문제만 정확히 이해하면 다른 더하기 DP문제들은 꽤 쉽게 풀릴것이다. 그림을 보면 파란색글씨로 + 1, + 2, +3 을 해놓은것을 볼 수 있다. 1, 2, 3더하기니까 이렇게 1, 2, 3을 기준으로 앞에 들어와야 할 수를 구해준다. 이게 가능한건 DP이기 때문에 가능하다. +1, +2, +3앞에 오는 수가 무엇이든간에 이미 1과 2와 3의 조합으로만 더해놨기 때문이다. 위의 그림에 5를 보면 이전에 4를 1과 2와 3의 조합으로 해놨기 때문에, 4에 조합된 개수를 그대로 가져오는걸 볼 수 있다. 이해가 안간다면 여러번보고.. 2021. 11. 2. [Swift][DP] 백준 2225번 (합분해) 요구능력 : DP에 대한 이해 코드설명 : 이해가 정말 잘되게 해주신 블로그 우선 구해야되는 배열의 개수가 얼마안되서 그냥 처음부터 끝까지 다 구해버리고 거기서 해당되는 배열[k][n]을 뽑아냈다. 위에 태그해놓은 블로그를 먼저 보고오면 어떤식으로 풀어야할지 감이 잡힌다. 2차원배열인걸 처음에 어떻게 알고 풀지라고 생각했는데,, DP는 입력이 2개가 반드시 들어와서 찾는거라면 2차원이 아닐까.. 라는 생각을 조심스럽게 해본다. 여튼 이제 2차원으로 푸는건 위에 블로그에서 설명해주신대로 표그려서 풀어야겠다.. 후기 : 어려운거 같은데,, 알고나면 이렇게 푸는방법도 있구나 싶은 문제였다. 많은 정보중에서 내가 이 문제를 다시 봤을 때 논리적으로 풀 수 있겠다 싶은 방법으로 풀었다. let nk = readL.. 2021. 11. 1. [Swift][DP] 백준 14051번 (퇴사) 요구능력 : DP에 대한 이해 코드설명 : 이 문제는 삼성SW역량테스트? 거기서 나온문제라고 한다. 1. 입력받기 let n = Int(String(readLine()!))! var t: [Int] = Array(repeating: 0, count: n + 1) var p: [Int] = Array(repeating: 0, count: n + 1) var dp = Array(repeating: 0, count: 1001) for i in 1...n { let TP = readLine()!.split(separator: " ").map{Int(String($0))!} t[i] = TP[0] p[i] = TP[1] dp[i] = p[i] //넣어놔야 아래코드에서 비교가능 } 2. DP코드 짜기 for i i.. 2021. 10. 8. 이전 1 ··· 3 4 5 6 7 8 다음
