2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 오늘 깔끔하게 프로그래머스 미로탈출 푸는게 목표였는데.... ^^흠 DP는 항상 어렵다 특히 for문을 잘 쓰는 bottom-up 방식은 생각이 안 난다 그래서 나는 항상 재귀함수를 구현한 뒤에 메모이제이션을 적용한다 DP는 어렵다 . . . #include #include using namespace std; int T, W; int plum[1005], cache[2][31][1005]; int fun..

https://www.acmicpc.net/problem/22114 22114번: 창영이와 점프 창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 www.acmicpc.net 오랜만에 푸는 DP문제 처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다 dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯 #include #include using namespace std; int n, k, l[100005], dp[2][..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 오랜만에 DP 기본문제 숫자가 커질 수 있으니 계산 과정에서 나머지 연산을 꼭 해줘야 한다 !! 처음에 최대 숫자까지 미리 계산해준 뒤 입력에 따라 출력만 제대로 해주면 끝 #include #define MOD 1000000009 int n, tc, dp[1000005] = { 0,1,2,4 }; int main() { for (int i = 4; i

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 전형적인 DP문제인 구간합 구하기이다 !! 1. 문제 정의 (x1, y1)부터 (x2, y2)까지의 직사각형 영역에 있는 element들의 합을 구한다 2. Subproblem & Recurrence (0,0) ~ (X2,Y2)까지의 구간합은 (X1-1,Y2)의 구간합+ (X2,Y1-1)의 구간합 - (X1-1,Y1-1)의 구간합으로 나타낼 수 있다(아래의 그림 참조)..

Maximum subarray problem이라는 문제가 있다 N개의 원소를 가진 배열이 있을 때, (i,j)의 연속되는 인덱스를 선택했을 때의 원소 최대 합을 구하는 문제이다 즉 [4, -2, 5, -4, 3, -7, -6, 10, 5]라는 배열이 있을 때 maximum subarray problem의 답은 7~8번째 원소값을 더한 15가 된다. 이 때 가능한 해결법은 약 세가지가 있다 1️⃣ 모든 인덱스 (i, j)에 대해 sum을 계산한 뒤 maximum값을 구한다 for(int i=0;i maxSum)maxSum = sum; } } 구간합을 구하기 위해 앞에서 구한 값을 활용해줬다. (i,j)의 구간 합 = (i,j-1)의 구간 합 + (j)의 원소 값인 점을 이용한다. 하지만 이 경우에도 시간복..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 정의 N줄에 걸쳐 3개의 숫자 중 최대 점수를 얻을 수 있는 숫자를 선택한다. 단, 이전에 선택했던 열과 인접한 열에 있는 숫자만 선택 가능하다. 2. Recursion&Subproblem K-1번째 줄에서 1번을 선택했다면 K번째 줄에서 1, 2번 중 큰 숫자를 선택한다 K-1번째 줄에서 2번을 선택했다면 K번째 줄에서 1,2,3번 중 큰 숫자를 선택한다 K-1번째 줄에서 3번을 선택했다면 K번째 줄에서 2,3번..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. 문제 정의 좌표 평면 내의 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다 이 때, 넓이를 구하기 위해 가장 큰 정사각형의 한 변의 길이를 구한다 위와 같은 그림에서 최대 정사각형의 한 변의 길이는 2이므로, 답은 4이다 2. Subproblem&Recursion 특정 좌표를 오른쪽아래 꼭지점으로 정사각형의 길이를 구한다고 할 때, 이 좌표의 북, 서, 북서쪽 좌표는 반드시 1이어야 한다. 그리고 좌표가 아래와 같을 경우, 0111001 -> 0111001 0111001 -..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분수열은 가장 긴 증가+감소 수열을 섞은 문제이다 맨 앞부터 가장 긴 증가 수열을 구하고, 맨 뒤부터 가장 긴 증가 수열을 구하면 i번째 원소에 대해 (현재 원소를 포함하는 가장 긴 증가 수열의 길이, 현재 원소를 포함하는(맨 뒤부터) 가장 긴 감소 수열의 길이)를 구할 수 있다 for문을 두번 돌아준 뒤 해당 값들의 합이 가장 큰 쌍을 찾아주면 되는 문제 #include int n,dp[3][1001],ans; int..