dp
[BOJ / DP] 13398 연속합 2
https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 13398 연속합 2 알고리즘 : 누적합 / DP 일단 연속합의 최대를 구하는 sum을 이용해 연속합1 의 답을 구해준 뒤, - dp[0][i]에는 배열의 앞에서부터 i번째까지의 최대연속합 - dp[1][i]에는 배열의 뒤에서부터 i번째까지의 최대연속합 을 구해줍니다. 그 뒤, 1~n까지 돌며 dp[0][k-1] + dp[1][k+1]로 k번째 수를 제외하였을 때 연속합의 최대를 갱신해 답을 구해줍니..
[BOJ / 메모이제이션 BFS] 2157 여행
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 2157 여행 알고리즘 : 메모이제이션 / BFS 기본적인 메모이제이션을 이용한 BFS 풀이입니다. 인접리스트를 이용하여 각 도시간 항로를 만드는데 도착지가 출발지보다 작은 경우는 추가하지 않습니다. (시간 절약) 메모이제이션 테이블은 DP[A][B]=K를 - A : 현재까지 들린 도시의 수 - B : 현재 도시 번호 - K : 최대 ..
[BOJ / 비트마스크 DP] 1102 발전소
www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1102 발전소 알고리즘 : 비트마스크 DP / BFS 비트마스크를 DP배열의 iterator로 사용하는 문제입니다. dp를 이용해 현재 적용중인 상태에서 이미 들린 상태이거나 이미 결과값을 초과한 경우 가지치기를 하면 됩니다. 문제에서 해결이 안되는 경우에는 -1을 출력하라고 했으나, 모든 발전소는 다른 모든 발전소를 킬 수 있으므로 즉, 키는 비용에 음수값이 주어지는 경우가 없으므로 -1을 출력하는 경우는 모든 발전소가..
[BOJ / DP] 15990 1,2,3 더하기 5
www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 15990 1,2,3 더하기 5 알고리즘 : DP 1차원 배열 DP로 시도하다가 점화식에 문제가 있다는 걸 발견하고 3차원 배열 DP로 바꾸었습니다. 같은 수를 두번 이상 연속해서 사용하면 안되므로 1차원 배열 DP에서 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 에서 dp[i-1]에서 +1로 끝나는 dp[i-2]를 빼고 dp[i-2]에서 dp[i-4]를 빼고 dp[i-3]에서 dp[i-6]을 빼려다 빼는 부분에서도 다시 빼야하는 경우가 있어..