Algorithm/Dynamic Programming

[백준 2156번] 포도주 시식 (C++)

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 포도주 시식 문제는 N이 최대 10,000이므로 모든 경우의 수를 계산하는 경우 시간 초과가 발생할 수 있습니다. 포도주 시식 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 테이블 d[i]는 i번째 포도주까지 시식했을 때의 최대 포도주의 양으로 정의했습니다. 초기 값 d[1] = 첫번째 포도주의 양, d[2] = 첫번째 포도주의 양 + 두번째 포도주의 양입니다. 연속으로 놓여있는 3잔을..

[백준 15486번] 퇴사 2 (C++)

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 본 게시글은 BJ 14501 퇴사, 15486 퇴사2를 참고하여 작성되었습니다. 퇴사 2 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍의 테이블 d[i]는 i번째 일까지 상담했을 때 얻는 최대 이익으로 정의하였습니다. i번째 상담 종료되는 날에, i번째 일까지 상담했을 때 얻는 최대 이익 + i번째 상담의 비용을 기록하면 됩니다. 단,..

[백준 10844번] 쉬운 계단 수 (C++)

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉬운 계단 수 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 0으로 끝나는 N 단계의 계단 수는 1로 끝나는 N - 1 단계의 계단 수와 같습니다. 마찬가지로, 9로 끝나는 N 단계의 계단 수는 8로 끝나는 N - 1 단계의 계단 수와 같습니다. 또한, i(1 ~ 8)로 끝나는 N 단계의 계단 수는 pre[i - 1] + pre [i + 1]입니다. (단, pre[j]는 j로 끝나는 N - 1 단계의 계단 수) d[i] = nxt[0] + nxt[1] + nxt[2] + nxt[3] + ... + ..

[백준 11055번] 가장 큰 증가 부분 수열 (C++)

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 가장 큰 증가 부분 수열은 n이 최대 1,000이므로 백트래킹을 이용하는 경우 시간초과가 발생할 수 있습니다. 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 부분 수열의 첫 원소는 어느 숫자든 가능하며, 이후의 원소는 이전 원소보다 커야합니다. 따라서 시작 원소 이후, 첫 원소보다 큰 원소들에 대해 가장 큰 증가 부분 수열..

[백준 1912번] 연속합 (C++)

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합 문제는 n이 최대 100,000이기 때문에 모든 구간합(Prefix Sum)을 구하는 경우 (100,000 * 100,001) / 2의 경우의 수에 대해 구간합을 구해야하기 때문에, 구간합의 시간 복잡도가 O(1)이어도 시간 초과가 발생할 수 있습니다. 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 알고리즘은 아래와 같습니다. 기존 수열의 합 + 현재 숫자가 현재 숫자보다 큰 경우 즉..

[백준 2193번] 이친수 (C++)

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이친수 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기의 과정으로 구분할 수 있습니다. 테이블 정의 이친수에서는 1이 연속으로 나타나지 않는다는 조건이 있기 때문에 0과 1을 구분할 필요가 있습니다. 이진수는 0또는 1로 끝날 수 있으므로, d[i][j]은 i자리이고, j로 끝나는 이친수의 개수라고 정의하였습니다..

[백준 12852번] 1로 만들기 2 (C++)

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1로 만들기 2 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. n에서 선택 가능한 경우의 수는 3가지 입니다. 3으로 나누기 2로 나누기 1 빼기 따라서 n/3, n/2, n-1 중에서 가장 적은 연산으로 1을 만들 수 있는 숫자를 선택하면 됩니다. 또한, 3으로 나누기, 2로 나누기, 1 빼기를 선택할 때마다 이전 숫자를 기록함으로써 경로를 추적할 수 있습니다. 아래는 Bottom-Up 방식의 다이나믹 프로그래밍을 이용한 코드입니다. #include using namespace std; ..

[백준 1149번] RGB거리 (C++)

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 집의 수가 최대 1000개이고, 각 집은 3개의 색을 선택할 수 있으므로, 백트래킹을 이용할 경우 시간초과가 발생할 수 있습니다. 다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기 구분할 수 있습니다. 테이블 정의 d[i][j]는 i번째 집의 색을 j로 칠할 때, 모든 집을 칠하는 비용의 최솟..