백준 2655번 - 가장 높은 탑 쌓기 가장 높은 탑 쌓기 문제의 경우 전형적인 dp문제 중 하나이다. 조건 중 하나가 밑의 블럭의 크기와 무게가 현재 블럭 보다 더 커야 한다는 조건이 있다. 이전의 위치한 블럭의 값 들과 계속해서 비교하면서 값을 업데이트해준다. 우선 시작하기전에 필자의 경우에는 넓이의 기준으로 내림차순으로 정렬했다. (물론 무게를 기준으로 정렬해도 된다.) 그래서 블럭의 이전의 값들과 비교하기 편하다. 내림차순이면 이전의 넓이는 항상 큰 값이 된다. 따라서 점화식은 아래와 같다. dp[i] i번째 블럭의 가장 높은 높이이다. if(올릴 수 있는 블럭이라면) { // 현재 블럭이 더 가볍고 부피가 작다면 dp[now] = max(dp[now], dp[prev] + height[now])..

백준 9465 스티커 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 문제의 경우 대각선으로 이동하는 경우 어떻게 많은 값을 가지고 이동할 수 있는가가 문제이다. 이전 퇴사 문제의 경우에도 선택하지 않을 경우가 있어서 스티커와 비슷한 문제라고 착각했다. 우선 조건부터가 많이 다르다. 퇴사문제의 경우 N이 1000개, 스티커의 경우 100000이다. 즉 일부분을 직접 방문해보면서 문제를 해결하기에는 시간초과가 발생한다는 의미이다. 그래서 dp..

백준 14501 퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사 문제이다. 각각의 걸리는 시간 만큼 일은 못하지만 그 사이에서 적절한 선택을 통해 최대의 수익을 올려야하는 문제이다. 이 문제를 풀면서 어려웠던 점은 다음 경우의 수를 선택안하고 다다음의 경우를 선택하여 최대의 수익을 올릴 수 있었다. 주의할 점 1. 무조건 다음 점이 아니라 다다음 점을 선택해도 최대가 될 수 있다는 점 1번을 해결하기 위해서 현재 위치에서 진행되는 시간을 더한 것 부터 최대 가능 시간까지 반복문을 돌렸다. 현재 위치 + 현재 업무가 걸리는 시간