www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이 문제는 전형적인 dp이면서 가장 긴 증가하는 배열을 구하면 된다. 기본 예제에서 확인해보자 3 7 5 2 6 1 4 여기서 가장 길게 증가하는 배열은 3 5 6이다 이 사이의 값들만 옮겨서 1 2 3 4 5 6 7로 바꾸어주면 된다. 3 5 사이로 4 3 밑으로 1, 2 6 뒤로 7 이렇게 되면 1, 2, 4 ,7만 옮기면 되기 때문에 4가된다. 그래서 이 문제는 가장 길면서 증가하는 배열의 수를 구한 다음 입력 ..

백준 1563 개근상 www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 전형적인 dp문제이다. 이전의 정보를 이용해서 풀어야하는데 문제를 맞고나서 다른 사람들의 풀이를 보니 대부분 다르게 풀어서 내가 푼 방법을 공유하려고한다. 우선 3차원 배열을 이용해 dp[일][지각의 수][연속된 결석의 수]로 표현해주었다. 해당 일에 지각의 수와 연속된 결석의 수의 개근상이 가능한 사람의 수가 된다. 그럼 배열로 나타낼 수 있는 경우의 수는 얼마나 될까? dp[요일][0][0] = d..

백준 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번을 해결하기 위해서 현재 위치에서 진행되는 시간을 더한 것 부터 최대 가능 시간까지 반복문을 돌렸다. 현재 위치 + 현재 업무가 걸리는 시간

백준 11052 카드 구매하기 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 카드 구매하기 문제의 경우 1장을 골랐을 때 최고의 가격, 2장을 골랐을 때의 최고의 가격 등을 구해주어서 문제를 해결할 수 있다. 아래의 예를 보자 10은 첫번째 카드, 9는 두번째 카드 ,,,, 쭉 진행한다. 1번째 카드의 경우 경우의 수가 1장 뿐이다. 2번째 카드 1 1, 2 자기 자체를 가지는 값 3번째 카드 1 2, 3 1번째 카드와 2번째 카드를 가졌을 때, 3번째 자기 자신..