728x90 중간에서 만나기2 [python] 백준 16287 Parcel https://www.acmicpc.net/problem/16287 문제 해결오직 4개를 쓰며 정확히 w의 무게를 맞추는 방법에 대해서 여러가지 방법을 생각해 볼 수 있다.DP, DFS ...무게가 엄청 클 수 있고 n이 상대적으로 작으므로 n개에서 4개를 고르는 것을 사용한다.그런데 4개를 고를 때 graph를 사용하여 dp를 만들기는 상당히 부담스럽다. 4차원 공간보다 2개씩 나누어 2차원 DP를 만들고 2차원 + 2차원 계산을 하는 것이 좋을 것이라 생각했다.하지만 dp[i][j] 의 value 값을 무엇을 쓸지 사실 의미가 크게 없었다. {0, 1}로 하고 (w-i-j )숫자가 나오는 조합을 N개 안에서 또 찾는 것은 시간복잡도가 상당했다.따라서 dp를 1차원으로 만들어서 확인을 하는 것이 좋.. 2024. 6. 22. [python] 백준 1208 부분수열의 합 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 정수의 최대 개수가 40개이므로 하나씩 계산을 하면 O($40^{40}$) = O(1.2089258e+64)이므로 무조건 시간초과이다. 하지만 연속된 부분수열의 합이 아니고 규칙이 있는 것도 아니기 때문에 하나씩 계산해야 할 수 밖에 없다. 그 결과 수열을 20개씩(절반씩) 잘라서 계산한 후 합이 0이 되는 개수를 더하는 방법을 생각할 수 있다. .. 2023. 6. 22. 이전 1 다음 728x90
