목록백준/Dynamic Programming (32)
mojo's Blog
[백준 15989] 1, 2, 3 더하기 4
문제 링크 => 15989번: 1, 2, 3 더하기 4 (acmicpc.net) 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 합을 나타낼 때 수를 1개 이상 사용한다는 것을 못봐서 약간의 뇌절을 했던 문제이다. 그럼 규칙성을 발견해보도록 한다. dp_1[x] => x = 1 + ( ) (( ) 안에 1, 2, 3 으로 구성)로 나타낼 때, ( ) 가 나타낼 수 있는 갯수 dp_23[x] => x = 2 + ( ) (..
[백준 15486] 퇴사 2
문제 링크 => 15486번: 퇴사 2 (acmicpc.net) 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net Dynamic Programming 문제이다. 이 문제는 1일 2일 ... N일 접근을 해서 O(N) 만에 해결하도록 해야 한다. 문제에 주어진 Input을 기반으로 설명하고자 한다. 이때 dp[x] 는 x일 일때의 최대 이익을 의미한다. x T[x] P[x] dp[x] 1 3 10 0 2 5 20 0 3 1 10 0 4 1 20 0 5 2 15 0 6 4 40 0 7 ..
[백준 11060] 점프 점프
문제 링크 => 11060번: 점프 점프 (acmicpc.net) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 끝지점까지 문제에서 주어진 조건에 맞게 이동할 수 있는 경우 최소로 점프한 횟수를 반환하고 이동할 수 없는 경우 -1 를 반환한다. i 번째에 점프할 수 있는 횟수를 A[i] 라고 할 때, 0 A[i]; cout
[백준 1519] 부분 문자열 뽑기 게임
문제 링크 => 1519번: 부분 문자열 뽑기 게임 (acmicpc.net) 1519번: 부분 문자열 뽑기 게임 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 + 게임 이론 문제이다. 게임 이론이라는걸 이번에 처음 알게 되었다. 플레이어 1이 무조건 지게되는(필패) 경우를 찾고 dp 값을 업데이트 하는것을 기반으로 이 문제를 접근해 보려고 한다. 처음으로 N 값이 10 미만인 경우에 대해 살펴보면 이 경우는 필패이다. => 문제의 조건에서 "진 부분 문자열이란 자기 자신을 제외한 모든 연속된 부분 문자열을 말한다." 라고 명시되어 있으므로 10 미만의 숫자는 부분 문자열이 존재하지 않으므로 고를 수 없다. 따라서 dp[ 1~..
[백준 13283] Daruma Otoshi
문제 링크 => 13283번: Daruma Otoshi (acmicpc.net) 13283번: Daruma Otoshi For each dataset, output in a line the maximum number of blocks you can remove. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 약간 이 문제 => 11049번: 행렬 곱셈 순서 (acmicpc.net) 랑 비슷한 느낌인데 재귀로 풀니 계속해서 시간초과를 받았습니다. (왜 그런지는 의문...? ㅠㅠ) 그래서 3중 for문으로 해결하였습니다. 일단, dp[x][y] 를 [x, y] 범위 내에서 제거할 수 있는 블럭의 수라고 하겠습니다. 풀이는 다음과 같습니다. 1. [0, 1], [1, 2], ... , [N-2, ..
[백준 22358] 스키장
문제 링크 => 22358번: 스키장 (acmicpc.net) 22358번: 스키장 첫 번째 줄에 다섯 개의 정수 $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$) 가 주어진다. 이후 $M$ 개의 줄에 각 코스의 정보가 세 개의 정수 $a_i, b_i, t_i$ ($1 \le a_i DAG 이다. 리프트를 타지 않는 경우(K = 0) 와 리프트를 한번 이상 타는 경우(K >= 1) 로 나눠서 해결할 수 있다. 2차원 배열 dp[x][y] 를..