DP29 [Swift][DP] 백준 1932번 (정수삼각형) 요구능력 : DP에 대한 이해 코드설명 : 문제를 읽고 우선적으로 생각해볼 수 있는건 dp[i]를 구하려면 이전에 어떤 값을 골랐는지가 중요하다는것이다. 삼각형에서 한줄을 i줄이라고 한다면 몇번째 수를 선택했는지가 중요한것이다. 이것을 보고 dp는 2차원 배열로 이루어지겠구나를 생각했다. 조건은 왼쪽대각선 혹은 오른쪽대각선으로만 선택할 수 있는것이다. 문제의 예제를 보고 8, 1, 0이 있는 줄을 dp[i]라고 생각해보면 이전 줄에 3, 8이 있다. 우선 8을 선택했을 때의 최대값을 구하기 위해서는 3에서 내려오는 방법밖에는 없다. 왼쪽 대각선으로 내려오는 것 밖에 없는것이다. 다음으로 1을 생각해보자. dp[i][1]을 구하는것인데 1은 왼쪽대각선과 오른쪽대각선 2가지가 모두에서 내려올 수 있다. 다.. 2021. 11. 9. [Swift][DP] 백준 2156번 (포도주 시식) 요구능력 : DP에 대한 이해 코드설명 : 문제의 핵심은 3잔연속으로 선택하면 안된다는점과 가장 많은양의 포도주를 마셔야한다는점이다. 보통 이렇게 숫자가 나열되어있고 가장많은양의~, ~~연속 이런식으로 나오면 DP의 2가지 요소가 충족해서 DP로 풀면된다. 6 10 13 9 8 1이 있다. 어차피 첫번째 dp의 최대값은 주어진 배열의 맨앞의 수이다. 쌓일 수 있는 값이 없기때문이다. dp[1] = arr[1] 마찬가지로 dp[2]도 3잔연속되는 경우가 없기에 dp[2] = arr[2]이다. 그럼 이제, dp[3]을 구해보자. dp[3]은 세번째 잔이기 때문에 문제의 조건을 다뤄줘야한다. 이렇게 세가지 경우의 수중 최댓값을 찾으면 그게 점화식의 완성이다. 점화식은 아래 코드에 적혀있습니다. 후기 : 규칙.. 2021. 11. 8. [Swift][DP] 백준 11057번 (오르막 수) 요구능력 : DP에 대한 이해 코드설명 : 수의 길이에 따른 오르막 수의 개수를 세는 문제이다. 오르막수는 오름차순과 비슷한데 같은 수가나와도 오르막수가 된다. 예를들면 1 2 3, 1 2 2은 오르막 수 인데, 1 2 1, 1 2 0은 오르막수가 아니다. 이 문제에서 주의깊게 봐야할 점은 004 이런것도 다 세줘야하는것이다. 수는 0으로 시작할 수 있다는게 이런의미. 수를 관리하기위한 문제는 2차원 배열을 생각하는게 좋다. 수의 끝을 기준으로 DP구하기가 수월하기 때문이다. DP[1][0]은 1자리수에 끝자리 수가 0으로 끝나는것이다. DP[3][5]는 3자리수에 끝자리 수가 5로 끝나는 것이다. DP[1][0]부터 DP[1][9]까지는 1을 삽입해준다. DP[1][0]은 1자리에 끝이 0으로 끝나는.. 2021. 11. 5. [Swift][DP] 백준 1303번 (동물원) 요구능력 : DP에 대한 이해 코드설명 : 2xn의 사각형이 있을때, 사자가 가로, 세로방향으로 있으면 안된다. 사자가 있을 수 있는 경우의수는 왼쪽, 오른쪽, 그리고 아예없을 경우이다. 이 문제는 사자를 배치하는 모든 경우의수를 구하는 문제이다. 점화식을 만들어보자. dp[i]를 구하려는데 i번째 배열에는 사자가 없을 수도 있다. 사자가 없는경우에는 이전 인덱스인 i - 1에서는 왼쪽에 사자가 있을 수도 있고 오른쪽에 사자가 없을 수도 있고 사자가 아예 없을 수도 있다. 이 문제는 사자를 배치할 수 있는 모든 경우의수를 구하는 것이므로, 조건별로 경우의수를 다 구해준다. 각각 다른 조건을 만족하는 경우의수들을 구하기 위해서는 dp를 2차원 배열로 사용해야한다. dp[i][0] = (dp[i - 1][1.. 2021. 11. 4. 이전 1 2 3 4 5 6 7 8 다음
