728x90 DP3 [백준][C] 11053번 가장 긴 증가하는 부분 수열 (동적 계획법) 전체 성공 코드 #include #define MAX_N 1000 int getMax(int a, int b) { return a > b ? a : b; } int dp(int n, int* arr) { int DP_table[n + 1]; int max_value = 1; DP_table[0] = 0; for (int i = 1; i 0; j--) { if (arr[i - 1] > arr[j - 1]) { DP_table[i] = getMax(DP_table[j] + 1, DP_table[i]); } } max_value = getMax(DP_table[i], max_value); } return max_value; } int main() { int n; scanf("\n%d", &n); int arr.. 2020. 12. 22. [백준][C] 11727번 2×n 타일링 2 (동적 계획법) 이전에 포스팅한 타일링 문제에서 약간의 변형이 된 문제이다. soyoonique.tistory.com/46?category=807751 [백준][C] 11726번 2×n 타일링 (동적 계획법) 가로 크기가 n인 곳을 채워야 할 때, 처음 타일을 세워서 놓는 경우 가로의 크기가 (n-1) 인 곳을 채우는 문제가 되고, 반대로 눞혀서 놓을 땐 (n-2) 곳을 채워야하는 문제가 된다. 이를 이용하여 점 soyoonique.tistory.com 다른 점이 있다면 이전에는 (n - 2) 크기의 타일을 부르는 경우가 1 x 2 타일을 가로로 나란히 놓은 경우밖에 없지만, 이번에는 정사각형을 놓는 경우가 추가되었다는 것이다. 즉, 점화식은 D[i] = D[i - 1] + 2 * D[i -2]이 되고 이전과 동일한 방.. 2020. 12. 21. [백준][C] 11726번 2×n 타일링 (동적 계획법) 가로 크기가 n인 곳을 채워야 할 때, 처음 타일을 세워서 놓는 경우 가로의 크기가 (n-1) 인 곳을 채우는 문제가 되고, 반대로 눞혀서 놓을 땐 (n-2) 곳을 채워야하는 문제가 된다. 이를 이용하여 점화식을 세우면 D[i] = D[i - 1] + D[i -2]가 되고 해당 문제를 푸는 방식은 재귀함수를 이용하거나 동적 계획법을 이용하면 풀 수 있다. 하지만, 실험해본 결과 재귀함수를 이용하여 제출하면 시간 초과의 결과가 나온다. 재귀함수를 이용하더라도 메모제이션을 사용한다면 통과할 수 있을 것 같긴하다! 또한 주의해야할 것이 처음의 풀이는 D[i] = D[i - 1] + D[i -2]를 저장하고 나중에 출력할 때 D[n]를 10007로 나누었는데 그렇게 하면 오버플로우가 나는지 오답이라고 뜨니! 저.. 2020. 12. 21. 이전 1 다음 728x90
