공부공간

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이분탐색으로 나무를 자르는 문제이다. 절단기의 H를 설정해주면 나무배열에서 H이상의 값을 가진나무들과 H의 차만큼 가져갈수있는 나무가..

N개의 지방에게 알맞는 예산을 분배하는 문제이다. 입력의 마지막에 돈이 주어지는데, 각자 원하는금액을 최대한 맞추어주면서, 내가가지고있는 금액 한도에서 분배해야한다. 즉, 요청값을 정렬한 후에 이분탐색으로 적절한 예산을 찾아주면된다. 두가지의 예외가 존재하는데, 1. 예산이 너무 많아서 모두 원하는만큼 주어도 되는경우 2. 예산이 너무 적어서 원하는금액중 가장 작은 금액으로도 못주는경우 만 이분탐색 전에 체크해주면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..

숫자들의 나열중 연속된 숫자중 부분합이 가장 큰 수를 출력하는 문제이다. 1. 모든 수가 음수인경우 (음수중 가장큰 한개를 선택해서 출력해준다) 2. 음수와 양수가 섞여있는경우 ( DP[N]을 구할때 DP[N-1]이 음수라면은 현재의 값을 DP[N]으로 설정해준다. 음수 + 양수는 그냥 양수보다 항상작기때문에)

삼각형을 내려오면서 가질수 있는 최대의 값을 구하는 문제이다. 내려올때에 이전 층의 대각선 방향만 고려하면 되기때문에, DP[N][N]을 구할때 DP[N-1][N-1] + NOW , DP[N-1][N]+ NOW 의 경우중 큰값을 가지고 업데이트 해준다. 맨처음과 끝은 비교해야할 대상이 한가지이므로 이경우만 처리해주면서 진행하면 된다.

계단을 오르면서 얻을수있는 점수의 최댓값을 구하는 문제이다. 맨 마지막을 꼭 밟으면서 연속된 3개의 계단은 밟지 못하는 규칙이 있으므로 1. 두칸을 오르고 맨마지막 직전의 계단을 밟고 마지막 계단을 밟은경우, 2. 두칸을 오르고 맨마지막 직전 계단 이전을 밟고, 직전계단을 밟고 마지막 계단을 밟은 경우로 나뉜다. 즉 dp[n]값을 구하기위해서 dp[n-2] + num[n] 값과 dp[n-3] + num[n-1] + num[n-2] 값중 큰값으로 업데이트해주면서 진행하면된다.

수열에서 연속되지 않은 3개 미만의 수를 고르면서 최댓값을 출력하는 문제이다. DP로 풀기위해서 점화식을 세워보니, 조건에서 연속하는 3개의 포도주는 마실수 없다고 제시하였다. 따라서 1. 현재 포도주를 마시지 않을경우 (DP[n-1]) 2. 현재 포도주는 마시고 바로 직전 포도주는 안마신경우 즉 n-2까지는 최대인경우 ( DP[n-2] + num[n] ) 3. 현재포도주와 직전포도주까지 마시고 연속해서 3잔은 못마시기때문에 n-3까지는 최대인경우 ( DP[n-3] + num[n] + num[n-1] ) 이 3가지중에 가장 큰 값을 DP[n]으로 선택하여서 업데이트 해주면 된다. N

DP 기본형이다. DP[i][j] 번째는 직전에 이동할수있는 장소의 최댓값에 현재 장소의 값을 더해서 저장해준다.

좌측상단에서 시작하여서 가본적이 없는 알파벳을 찾아서 상하좌우로 진행하였을때에, 최장거리를 출력하는 문제이다. 문제는 'Z'-'A' 크기(25)만큼의 visit배열을 생성하고 DFS를 돌리면서 가본적이 없는 알파벳으로 진행하면서 PATH값을 최대로 갱신한다. 탐색할 노드에 대한 방문처리만 잘해주면 쉽게 풀리는 문제였다.