백준 7453_합이 0인 네 정수(C++)
www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net [문제 풀이] 단순 구현을 이용하여 문제를 풀었습니다. 이 문제는 4중 반복문을 이용하게 되면 시간 초과가 나게 됩니다. 따라서 이 문제를 풀기 위해 시간을 줄이는 것에 초점을 맞췄습니다. 코드의 로직은 크게 두 가지입니다. 먼저 A, B, C, D 네 가지를 두 가지로 나누어 줍니다. 두 번째로 나눠진 것에서 합이 0이 되는 걸 찾습니다. 코드 설명 A, B, C, D를 (A, B) 합의 배..
백준 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..
