본문 바로가기

dynamic programming29

[Problem Solving] BOJ 2342: Dance Dance Revolution 문제 출처: https://www.acmicpc.net/problem/2342 DDR 게임 지시 사항이 주어졌을 때, 주어진 지시 사항을 만족하는 데 사용하는 최소의 힘을 출력하는 문제다. 우선 DP테이블을 다음과같이 정의할 수 있다.DP[i][left][right]는 i번째 지시 사항까지 수행했을 때, 왼발이 left에 있고, 오른발이 right에 있는 경우 누적된 최소의 힘이다. 지시 사항이 총 N개 라면, DP[N][left][right] 중에 가장 작은 것을 고르면 된다. 다음 지시 사항이 next 라면, dp[i + 1][next][right], 와 dp[i + 1][left][next]를 갱신할 수 있다.dp[i + 1][next][right]를 갱신할 때는, 기존 dp[i + 1][next].. 2025. 8. 25.
[Problem Solving] BOJ 1106: 호텔 문제 출처: https://www.acmicpc.net/problem/1106 호텔의 고객을 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값을 구해야한다. 먼저 DP테이블을 정의하자면,DP[i]는 i명의 고객을 늘이기 위해 필요한 돈의 최솟값이다.5명을 늘리는데 3원이 들고, 1명을 늘리는데 1원이 든다면, dp[5]전 까지는, 5명을 늘리는데 사용해야 하는 금액인 3원을 쓰지 않는다. dp[4]를 계산할 때는 굳이 5명을 늘리는데 사용하는 금액은 취급하지 않고, 4이하의 인원수를 늘리는데 사용하는 금액만 쓰기 때문에 dp[4]는 4다. 그리고 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값이기 때문에, C명 이상 늘이기 위해 투자해야 하는 금액 중 최솟값을 고르면 된다. 이는 min(DP[C:].. 2025. 8. 18.
[Problem Solving] BOJ 2240: 자두나무 문제 출처: https://www.acmicpc.net/problem/2240 예제 입력에 대한 DP 테이블은 다음과 같이 구성할 수 있다. 행은 지난 초를 의미하고, 열은 사람이 움직인 횟수를 의미한다. dp[i][j]는 i초까지 j번 움직였을 때, 얻을 수 있는 최대 자두 수를 의미한다. 처음에 사람은 1번 나무에 서있기 때문에 움직이지 않는다(j가 0)면 시간이 지나면서 1번 나무에서 떨어지는 것만 받는다. (t - 1) 시점까지 사람이 w번 움직였을 수도 있고, (w - 1)번 움직였을 수도 있다. t시점까지 w번 움직인 상태라면 "(t - 1) 시점까지 w번 움직이고 그 자리에서 1초 가 지난 것" 일 수도 있고, "(t - 1) 시점까지 (w - 1)번 움직이고 1초가 지나면서 1회 더 움직.. 2025. 8. 3.
[Problem Solving] BOJ 1562: 계단 수 문제 출처: https://www.acmicpc.net/problem/1562 0이 아닌 수로 시작하며, 0 부터 9까지 숫자가 모두 등장하는, 길이가 N인 계단수의 개수를 구하는 문제이다. 이 문제를 풀기 앞서서, BOJ 10844: 쉬운 계단 수 를 먼저 풀어보면 계단 수 문제가 DP로 어떻게 풀리는지 감을 잡을 수 있다. DP테이블은 다음과 같이 정의된다.DP[n][i][bitmask]: 계단 수의 길이가 n이고, 가장 오른쪽의 숫자가 i이며, 사용된 숫자 정보가 bitmask와 같을 때 계단 수의 개수 출력부를 먼저 보자.result += dp[N][i][1111111111(비트마스크)]이것은 계단수의 길이가 N이면서 가장 오른쪽 숫자가 i이며 문제에서 원하는대로 모든 숫자가 사용된 경우를 모두 .. 2025. 7. 28.
[Problem Solving] BOJ 2056: 작업 문제 출처: https://www.acmicpc.net/problem/2056 수행해야 할 작업이 N개 있고 각각의 작업마다 걸리는 시간이 있다.작업들 사이에는 선행관계가 있어서 어떤 작업을 수행하기 위해서 반드시 먼저 완료되어야 할 작업들이 있다.K번 작업에 대해 선행관계에 있는, 즉 K번 작업보다 먼저 완료되어야 하는 작업들의 번호는 K보다 작다.1번 작업은 선행관계에 있는 작업이 없다.모든 작업을 완료하기 위해 필요한 최소 시간을 구해야 한다. 선행 관계가 없는 작업들은 동시에 수행 가능하다. 먼저 작업의 선행 관계를 그래프로 표현한 후, 위상정렬로 topology를 얻는다.topology를 사용하여 dp테이블을 채워야 한다. 먼저 dp테이블을 정의하자면dp[i]는 i번째 작업 수행 이후에 수행해야.. 2025. 7. 20.
[Problem Solving] BOJ 13398: 연속합 2 문제 출처: https://www.acmicpc.net/problem/13398 배열이 있을 때, 연속된 몇 개의 수를 선택했을때 그것들의 합의 최댓값을 구하는데, 중간에 하나의 값을 제거할 수도 있고 제거하지 않을 수도 있다. 제거를 고려하지 않은 DP 테이블과 제거를 고려한 DP 테이블을 각각 만들어야한다. 제거를 고려하지 않은 DP 테이블을 dp1이라고 하자.dp1[i]는 i번째 숫자까지 고려했을 때, i번째 숫자를 포함시키는데, 앞에서 구한 부분 누적합인 dp1[i - 1]에 더한 것과 그냥 i번째 숫자 자체 중 더 큰것을 고르는 것이다."dp1에서 가장 큰 원소" == "제거 없이 연속된 몇 개의 수를 선택한 경우 그것의 최댓값" 이 된다. 제거를 고려한 DP 테이블을 dp2라고 하자.dp2[i.. 2025. 7. 13.
[Problem Solving] BOJ 2629: 양팔저울 문제 출처: https://www.acmicpc.net/problem/2629 N개의 추가 주어져있고, g개의 구슬이 주어져 있을 때, 각각의 구슬의 무게를 모른다고 가정했을때, 추를 이용해서 무게를 알아낼 수 있는지를 확인하는 문제이다. 구슬의 무게를 알아내는 방법은 여러 개의 추를 사용해서 수평을 만드는 것이다. 3g짜리 구슬의 무게를 모른다고 가정했을 때 1g과 4g짜리의 추가 있다면왼쪽에 구슬과 1g 추를 놓고 오른쪽에 4g짜리 추를 놓는다면 구슬이 3g임을 알 수 있다. 따라서 구슬의 무게를 알아낼 수 있다는 것은 여러 개의 추의 무게를 적절히 더하기와 빼기를 하여 구슬의 무게와 같게 할 수 있다는 것이다. dp[i]는 i g짜리 구슬이 추를 사용하여 무게를 파악할 수 있는지에 대한 것이다.dp.. 2025. 7. 6.
[Problem Solving] BOJ 2515: 전시장 문제 출처: https://www.acmicpc.net/problem/2515 그림을 1열로 세워놓았을 때 세로 S만큼 보이는 그림을 판매 가능 그림이라고 한다. 판매 가능 그림의 합이 최대가 될때 그 최댓값을 구하는 문제이다. 이 문제는 DP와 이분탐색으로 풀 수 있다. 판매 가능 그림 세트를 만들어서 맨 앞에다가 둔다고 생각하면 된다.DP테이블을 정의하자면, 그림의 높이를 기준으로 오름차순으로 정렬했다고 했을 때,DP[i]는 i번째 그림까지 취급할 때, 판매 가능 그림의 합의 최댓값이다. H 기준 오름차순으로 정렬된H = {8, 10, 15, 17, 20, 26}C = {230, 100, 80, 200, 75, 80}의 예시가 있다고 하자. 1)일단 DP[0] = 230이다. 2)H[0:1]에서 H[.. 2025. 6. 30.
[Problem Solving] BOJ 2302: 극장 좌석 문제 출처: https://www.acmicpc.net/problem/2302 N개의 좌석이 1열로 있을 때, VIP는 지정좌석에 앉을 수 있고 나머지 관객은 인접한 칸에 옮겨 앉을 수 있다고 한다. 사람들이 좌석에 앉는 모든 경우의 수를 구하는 문제이다. dp[i]: i번째 좌석까지만 존재할 때 사람들이 좌석에 앉는 경우의 수 이다. 테스트케이스 처럼 9개의 좌석이 존재하고, 4번과 7번 좌석이 VIP석이라고 하자. 1번 좌석까지만 존재할 때, 모든 경우의 수는1로 1가지 이다. 2번 좌석까지만 존재할 때, 모든 경우의 수는1 22 1로 2가지 이다. 3번 좌석까지만 존재할 때, 모든 경우의 수는1 2 32 1 31 3 2로 3가지 이다. 4번 좌석까지만 존재할 때, 4번 좌석은 VIP석이므로 모든 경.. 2025. 6. 23.
[Problem Solving] BOJ 1495: 기타리스트 문제 출처: https://www.acmicpc.net/problem/1495 i번째 곡을 연주하기 전에 현재 볼륨 P에서 V[i]만큼 줄이거나 V[i]만큼 키워야할 때, 마지막 곡의 볼륨의 최댓값을 구하는 문제이다.볼륨은 최소 0, 최대 M어야하고, 중간에 범위를 벗어나면 안된다. 이 문제는 2차원 DP로 풀 수 있다.DP테이블을 다음과 같이 정의할 수 있다.DP[i][j]: i번째 곡을 연주할때 j라는 볼륨으로 설정될 수 있는지에 대한 여부 (true / false) 풀이 과정은 다음과 같다. 1.V[0] = S일 때, DP[0][V[0]] 를 true로 설정한다. 2.0 N - 1)0 M)인 i, j에 대하여 DP[i][j]가 true일 때,j + V[i + 1]가 M이하라면 -> DP[i + .. 2025. 5. 19.
[Problem Solving] BOJ 2533: 사회망 서비스(SNS) 문제 출처: https://www.acmicpc.net/problem/2533 친구 관계 트리가 주어졌을 때, 모든 노드가 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 어답터 수를 구하는 문제이다.얼리 어답터는 인접한 모든 노드에 새로운 아이디어를 알릴 수 있다. 이 문제는 DP + DFS 방식으로 해결 할 수 있다. 우선 DP 테이블을 정의해야한다. DP[i][0]: i번째 노드가 얼리 어답터가 아닌 경우, 이 노드가 루트 노드인 서브트리의 최소 얼리 어답터 수DP[i][1]: i번째 노드가 얼리 어답터인 경우, 이 노드가 루트 노드인 서브트리의 최소 얼리 어답터 수 부모 노드가 얼리 어답터가 아니라면 자식 노드는 반드시 얼리 어답터여야 한다.-> DP[parent][0] += DP[child][.. 2025. 5. 11.
[Problem Solving] BOJ 15990: 1, 2, 3 더하기 5 문제 링크: https://www.acmicpc.net/problem/15990 n이라는 수가 1과 2와 3의 합으로 이루어 질 때, 더해지는 수가 연속적이지 않은 경우의 수를 구하는 문제이다. dp테이블을 다음과 같이 정의할 수 있다.dp[n][i]는 수의 합이 n일 때, 마지막으로 더해진 수가 i인 경우의 수이다.따라서dp[n][1] = dp[n - 1][2] + dp[n - 1][3] (1 + n - 1 = n)dp[n][2] = dp[n - 2][1] + dp[n - 2][3] (2 + n - 2 = n)dp[n][3] = dp[n - 3][1] + dp[n - 3][2] (3 + n - 3 = n)라고할 수 있다. 결과로 dp[n][1] + dp[n][2] + dp[n][3] 를 출력하면 된다... 2025. 3. 29.
[Problem Solving] BOJ 5557: 1학년 문제 링크: https://www.acmicpc.net/problem/5557 N개의 수가 주어졌을 때, 첫 번째 수 부터 N - 1번째 수를 더하거나 빼는데 중간에 음수나 20을 넘는 수가 나오면 안된다는 가정 하에 N번째 수를 만들 수 있는 경우의 수를 구하는 문제이다. DP테이블은 다음과 같이 정의한다.DP[i][j]: 첫 번째 수 부터 i번째 수를 사용하여 j를 만들 수 있는 경우의 수, 단 j는 0보다 크고 20보다 작은 수이다. DP[0][vec[0]] = 1로 초기화 한다.0번째 수 하나 만으로 0번째 수를 만들 수 있기 때문이다. i = 0 ~ N-3 까지 다음을 수행한다.j = 0 ~ 20 까지 j - vec[i + 1]이 0 이상이라면DP[i + 1][j - vec[i + 1]] += .. 2025. 3. 17.
[Problem Solving] BOJ 16194 : 카드 구매하기 2 문제 링크 : https://www.acmicpc.net/problem/16194 P[i]는 카드 i개가 들어있는 카드 팩의 가격일 때, 카드 N개를 구매하기 위해 지불할 최소 금액을 구하는 문제이다.DP[i]는 카드 i개를 구매하기 위해 지불할 최소 금액이다. dp[i]는 초기값으로 P[i]로 설정한 후,dp[i] = min(dp[i], dp[j] + dp[i - j]) [1 를 갱신해주면 된다. i개는 j + (i - j)개 이기 때문에i개를 구매하기 위해 지불할 최소 금액 = j개를 구매하기 위해 지불할 최소 금액 + (i - j)개를 구매하기 위해 지불할 최소 금액이다. #include #include #include #include #include #include #define endl '\n'.. 2025. 2. 25.
[Problem Solving] BOJ 5582 : 공통 부분 문자열 문제 링크 : https://www.acmicpc.net/problem/5582 가장 긴 공통 부분 문자열의 길이를 구하는 문제이다.dp[i][j]는 s[j - 1]와 t[j - 1]이 같을 때, s[:i]와 t[:j]의 가장 긴 공통 부분 문자열의 길이가 된다.따라서  s[j - 1] == t[j - 1]일 때, dp[i][j]를 dp[i - 1][j - 1] + 1로 설정한다.dp테이블을 다 채우고, 테이블 내 가장 큰 값이 답이 된다. import sysread = sys.stdin.readlines = read().rstrip()t = read().rstrip()answer = 0dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]for i in range.. 2025. 2. 21.

티스토리툴바