다이나믹프로그래밍6 [Swift][DP] 백준 13398번 (연속합 2) 요구능력 : DP에 대한 이해 코드설명 : 이 문제는 연속합 문제를 선행학습 하고 오셔야 이해가됩니다. 문제의 핵심 1. 연속합 2. 수를 하나 제거할 수 있다. 3. 수를 제거하지 않을 수도있다. 이 문제는 연속합이기 때문에 연속적으로 합을 구해줘야 하는데 수를 하나 뺄수 있다. 중요한점은 꼭 왼쪽에서 부터 시작한다는 생각을 버려야 한다. 만약에 -35라는 수를 빼고 연속합을 구하고싶다면 -35를 기준으로 가장 왼쪽에있는값 10부터 6까지의 연속합과 가장오른쪽에 있는값 -1부터 12까지의 연속합을 구해주면 된다. 이렇게 하면 왼쪽부터 -35만빼고 연속합을 모두 고려할수 있는것이다. 10 -4 3 1 5 6 -35 12 21 -1 n = 정수를 입력받는 부분 arr = n개의 정수로 이루어진 수열 dp_.. 2021. 11. 22. [Swift][DP] 백준 1303번 (동물원) 요구능력 : DP에 대한 이해 코드설명 : 2xn의 사각형이 있을때, 사자가 가로, 세로방향으로 있으면 안된다. 사자가 있을 수 있는 경우의수는 왼쪽, 오른쪽, 그리고 아예없을 경우이다. 이 문제는 사자를 배치하는 모든 경우의수를 구하는 문제이다. 점화식을 만들어보자. dp[i]를 구하려는데 i번째 배열에는 사자가 없을 수도 있다. 사자가 없는경우에는 이전 인덱스인 i - 1에서는 왼쪽에 사자가 있을 수도 있고 오른쪽에 사자가 없을 수도 있고 사자가 아예 없을 수도 있다. 이 문제는 사자를 배치할 수 있는 모든 경우의수를 구하는 것이므로, 조건별로 경우의수를 다 구해준다. 각각 다른 조건을 만족하는 경우의수들을 구하기 위해서는 dp를 2차원 배열로 사용해야한다. dp[i][0] = (dp[i - 1][1.. 2021. 11. 4. 이전 1 2 다음