Deff_Dev

문제https://www.acmicpc.net/problem/3273 문제 설명n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 입력첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)출력문제의 조건을 만족하는 쌍의 개수를 출력한다.풀이이 문제는 입력된 n개의 숫자들 중 두 수의 합이 x가 될 수 있는 모든 경우의 수를 구하는 문제이다. O(n^2)으로 풀이하게 되면 시간 초과가 나오기 때문에 더 효율적인 방법으로 풀..

https://www.acmicpc.net/problem/1475 문제 설명다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)입력첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.출력첫째 줄에 필요한 세트의 개수를 출력한다. 풀이입력된 roomNumber를 string으로 변환하여, 해당 문제를 풀이했다. 입력된 roomNumber의 각 번호 갯..

문제제https://www.acmicpc.net/problem/11726풀이점화식- dp[i] = dp[i - 1] + dp[i - 2]#include using namespace std;int dp[1001] = { 0, };int main() { int n; cin >> n; dp[1] = 1; dp[2] = 2; for (int i = 3; i

문제https://www.acmicpc.net/problem/14501풀이이 문제는 다이나믹 프로그래밍 문제이다. n부터 시작하여 각 상담에 대한 최댓값을 구하는 방법을 사용했다. dp[i] = max (dp[i + 1], dp[ t[i] + i] + v[i]] 여기서 상담을 할 수 없는 날이라면, dp[i + 1] 값을 저장한다.#include #include #include using namespace std;int dp[17] = { 0, };int main() { int n; cin >> n; vector t(n + 1); vector v(n + 1); for (int i = 1; i > t[i] >> v[i]; } for (int i = n; i >= 1; ..

문제https://www.acmicpc.net/problem/11053풀이이 문제는 다이나믹 프로그래밍 문제이다. 점화식 dp[i] = max(dp[j] + 1, dp[i]) 여기서 모든 요소들은 자기 자신을 수열에 포함하므로 초기 값을 1 설정한다.#include #include using namespace std;int dp[1001] = { 0, };int main() { int n; cin >> n; vector vec(n + 1); for (int i = 1; i > vec[i]; dp[i] = 1; } int maxCount = 1; for (int i = 2; i = 1; j--) { if (vec[j]

문제https://www.acmicpc.net/problem/1463 풀이이 문제는 다이나믹 프로그래밍 문제이다. dp[i] = min(dp[i+1] + 1, dp[i]) (모든 i에 대해)dp[i] = min(dp[2i] + 1, dp[i]) (i가 2의 배수일 때)dp[i] = min(dp[3i] + 1, dp[i]) (i가 3의 배수일 때)#include #include #include using namespace std;int dp[1000001] = { 0, };int main() { int n; cin >> n; for (int i = n; i >= 1; i--) { if (dp[i - 1] == 0) { dp[i - 1] = dp[i] + 1;..

문제https://www.acmicpc.net/problem/2579풀이다이나믹 프로그래밍 문제이다. dp[1] = stair[1];dp[2] = stair[1] + stair[2];dp[3] = max( stair[1] + stair[3], stair[2] + stair[3])dp[n] = stair[n] + max (dp[n - 2], dp[n - 3] + stair[n -1])#include #include using namespace std;int dp[301] = { 0, };int main() { int n; cin >> n; vector vec(n + 1); for (int i = 1; i > vec[i]; } dp[1] = vec[1]; dp[2] = dp[1] + vec[2]; dp[3..

문제https://www.acmicpc.net/problem/2839 풀이이 문제는 상근이가 3kg와 5kg 봉지를 사용하여 정확히 N kg의 설탕을 배달할 때, 최소한의 봉지 개수를 구하는 프로그램을 작성하는 문제다. 다이나믹 프로그래밍을 이용하여 풀이하였다. dp[3] = dp[5] = 1dp[n] = min (dp[i], dp[n - 5] + 1 )#include #include #include using namespace std;int dp[5001] = { 0, };int main() { int n; cin >> n; dp[3] = dp[5] = 1; for (int i = 6; i