백준 2143_두 배열의 합(C++)
www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net [문제 풀이] 메모제이션을 이용하여 문제를 풀었습니다. 이 문제는 입력된 A, B 배열의 연속 된 부분 배열의 합 중에 두 부분 배열의 합이 T와 같은 부분 배열의 개수를 구하는 문제였습니다. 문제의 로직은 A, B의 모든 합을 저장하여 정렬한 후 합의 경계를 찾아 경우의 수를 찾는 방식으로 구현하였습니다. 코드 설명 A 배열에 값을 ..
백준 2096_내려가기(C++)
www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net [문제 풀이] dp를 이용하여 문제를 풀었습니다. 이 문제는 N X 3의 맵을 내려가며 최대 합과 최소 합을 구하는 문제였습니다. 최댓값, 최솟값을 구하기 위해 N X 3 dp배열을 선언할 경우 메모리 초과가 나게 됩니다. 따라서 max_dp[3], min_dp[3] 배열을 두어 한 줄씩 내려오며 각각 최댓값, 최솟값들을 저장해주면서 내려오는 식으로 문제를 해결했습니다. [코드] #include #include using n..
