Problem Solving/DP 썸네일형 리스트형 BOJ 14720 - 우유 축제 문제 링크https://www.acmicpc.net/problem/14720 문제 해결 1. DP[i][j] = i번 째 우유 상점이고, 이전에 j 우유를 먹었을 때의 최대 우유 개수. 2. 딸기 -> 초코 -> 바나나 -> 딸기 -> 초코 .... 이런 특정한 규칙을 지켜야 하므로 이전에 먹은 우유의 정보를 저장하고 있어야한다. 주의할 점 || 생각해볼 점 1. 시작은 딸기 우유이므로, 딸기 우유가 없으면 0을 출력해야 한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 4811 - 알약 문제 링크https://www.acmicpc.net/problem/4811 문제 해결 1. DP[i][j] = 온전한 알약 i개와 반쪽짜리 알약 j개가 있을 때의 문장의 경우의 수 주의할 점 || 생각해볼 점 1. 처음엔 DP를 이용하지 않고 그냥 완전탐색을 해서 시간초과가 났다. 2. 완전한 알약이 없거나, 하나만 있으면서 반쪽짜리 알약이 없다면 경우의 수는 한 가지다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 9465 - 스티커 문제 링크https://www.acmicpc.net/problem/9465 문제 해결 1. 스티커를 규칙에 맞춰서 뗄 때, 떼어낸 스티커의 점수 합의 최대값을 구해야한다. 2. DP[i][j] = 스티커 (i, j)에서 최대값. 주의할 점 || 생각해볼 점 1. 1열과 2열에서 시작한 값이 다르므로 두 번 탐색한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2186 - 문자판 문제 링크https://www.acmicpc.net/problem/2186 문제 해결 1. 임의의 칸에서 시작해서 상하좌우로 1~K만큼씩 움직일 때마다 만나는 문자를 차례로 이었을 때, 주어진 문자열과 같은 경우의 수를 구하는 문제. 2. DP[i][j][k] = 문자판 좌표 (i, j)에 있는 문자와 주어진 문자열 S의 S[k]와 같을 때의 경우의 수. 주의할 점 || 생각해볼 점 1. DP 테이블을 만들 때, k의 범위가 최대 80까지임을 간과하면, 많은 수의 "틀렸습니다"를 획득할 수 있다. 2. BFS, DFS 모두 해를 구할 수 있다. 하지만 BFS로 문제를 해결할 시 메모리 초과에 걸리게 되어서 DFS+DP로 구현했다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1915 - 가장 큰 정사각형 문제 링크https://www.acmicpc.net/problem/1915 문제 해결 1. 직사각형 내에서 1로 된 가장 큰 정사각형의 넓이를 구하는 문제. 2. DP[i][j] = (i, j)에서 가장 큰 정사각형의 한 변의 길이. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2157 - 여행 문제 링크https://www.acmicpc.net/problem/2157 문제 해결 1. 항로를 통해서 이동할 때, 이용할 수 있는 가장 큰 기내식 점수의 합을 구하는 문제. 2. DP[i][j] = i번 째 도시에서 j번 이동했을 때의 가장 큰 기내식 점수의 합. 주의할 점 || 생각해볼 점 1. 항상 도시의 숫자가 증가하는 방향으로 이동한다. 2. 시작 점도 이동 횟수에 포함되어 있다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1126 - 같은 탑 문제 링크https://www.acmicpc.net/problem/1126 문제 해결 1. 주어진 블럭을 사용해서 두 탑을 만들 때, 높이가 같으면서 가장 높게되는 높이를 구하는 문제. 2. DP[i][j] = i번 째 블럭을 사용하여 (탑1의 높이 - 탑2의 높이) = j가 되는 가장 높은 높이. 주의할 점 || 생각해볼 점 1. 블럭의 높이의 차를 인덱스로 사용하는 문제이므로, 높이의 차가 음수가 되서는 안된다. 2. 두 탑이 서로 자리가 바뀔 수 있으므로 값은 두 배가 나온다. 그러므로 2로 나눈 것이 답이 된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1937 - 욕심쟁이 판다 문제 링크https://www.acmicpc.net/problem/1937 문제 해결 1. 상하좌우를 움직여서 현재보다 증가하는 방향으로 나아가는 가장 긴 거리를 구하는 문제. 2. DP[i][j] = (i, j)에서 출발했을 때, 도달할 수 있는 가장 긴 거리. 주의할 점 || 생각해볼 점 1. 주로 한 방향으로 증가하는 문제만이 DP라고 생각하기 쉽기 때문에, 상하좌우 움직이는 이 문제에 대해서 DP를 생각하기 쉽지가 않다. 2. 하지만 어느 점에서 출발하든, (i, j)를 지나게되면 (i, j)로 부터 도달할 수 있는 최장 거리는 같게된다. 3. 만약 그냥 DFS만을 사용하게되면 의 시간이 소요된다.(정점의 개수를 N*N이라하고 전체 다 이동한다 생각하면 N*N만큼 이동할 수 있으므로) 참고 - ※.. 더보기 BOJ 9177 - 단어 섞기 문제 링크https://www.acmicpc.net/problem/9177 문제 해결 1. DP 문제. DP[i][j] = 처음 문자열의 i 인덱스까지와 두 번째 문자열의 j 인덱스까지 섞어서 만든 문자열이 비교할 문자열과 일치하는 가에 대한 값 저장. 주의할 점 || 생각해볼 점 1. 비교할 문자열의 처음부터 차례대로 비교하면 될 것이라고 생각하기 쉽다. 하지만 만약 처음 문자열과 두 번째 문자열이 같은 문자를 가진다면 어느 것을 골라야할 지 명확해지지 않는다. 그러므로 DP를 사용해서 문제를 해결해야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1102 - 발전소 문제 링크https://www.acmicpc.net/problem/1102 문제 해결 1. bitmask DP 를 이용해서 문제 해결. dp[i] = i는 켜져있는 공장들과의 or 연산값 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 3 4 다음