문제 출처 : https://www.acmicpc.net/problem/2631 풀이과정어제 푼 문제와 똑같이 LIS(최장 부분 증가 수열)에 관한 문제이다. 아직 LIS 개념을 정확히 모르겠다. 더 찾아봐야겠다.DP[i] 를 i번째 원소를 끝으로 가지는 배열이 가질 수 있는 최장 부분 증가 수열의 길이라고 할 때, 정답을 출력하려면 입력 배열의 총 길이에서 최장 부분 증가 수열의 길이를 빼면 된다. 소스코드12345678910111213141516171819202122232425262728293031#include #pragma warning(disable:4996) int children[201], DP[201]; int main(){ int N,max=0; scanf("%d", &N); for (i..
문제 출처 : https://www.acmicpc.net/problem/2579 풀이과정 DP[i] 를 i번째 계단을 밟을 경우 최대로 얻을 수 있는 점수라고 한다.3번째 계단일 경우에는 2, 3번째 계단을 밟을 경우와 1, 3번째 계단을 밟을 경우를 비교하여 큰 값을 저장한다.4번째 이후로는 현재 계단만 밟을 경우와 현재, 이전 계단을 밟을 경우를 비교하여 큰 값을 저장한다. 소스코드 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;int DP[301], stair[301]; int main(){ int n; cin >> n; for (int i = 1; i > stair[i]; }..
문제 출처 : https://www.acmicpc.net/problem/2156 풀이과정 DP[i] 를 i번째 포도주 잔까지 최대로 마실 수 있는 양이라 한다.이 문제는 3가지의 경우로 나누어서 생각한다.1. 현재 포도주를 마시지 않는 경우 2. 현재 포도주를 마시고 이전 포도주를 마시지 않는 경우 ( o x o )3. 현재 포도주와 이전 포도주를 마시는 경우 ( x o o )3가지의 경우 중 가장 큰 값을 찾는다. 소스코드 12345678910111213141516171819202122232425262728293031#include #include using namespace std;int DP[10001], wine[10001]; int main(){ int n; cin >> n; for (int i..
문제 출처 : https://www.acmicpc.net/problem/9095 풀이과정 DP[i] 는 i를 1, 2, 3 의 합으로 나타내는 방법의 수라고 생각한다.수작업으로 DP[1], DP[2], DP[3] 을 구해보니 DP[4]는 DP[1], DP[2], DP[3]의 합으로 나타낼 수 있다는 생각이 들었다.소스코드 123456789101112131415161718192021222324252627#include using namespace std; int DP[11]; int main(){ int T,n; cin >> T; DP[1] = 1; DP[2] = 2; DP[3] = 4; for (int i = 4; i > n; cout
문제 출처 : https://www.acmicpc.net/problem/10164 풀이과정 DP[n][m] : (n,m) 까지 올 수 있는 경로의 수를 저장하는 배열DP[n][m] = DP[n-1][m] + DP[]n][m-1] 라는 점화식 이용0,0 부터 K값을 가진 x,y 까지의 경로의 수와 x,y 부터 n,m 까지의 경로의 수를 곱하면 답이 된다는 접근까지 했다. 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include using namespace std; int DP[16][16]; // 해당 위치까지 올 수 있는 경로의 개수int N,M,K..
문제출처 : https://www.acmicpc.net/problem/10163색종이 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초64 MB143078267855.483%문제평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이 때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 중 하나이다. 그림-1은 1번, 2번, 3번 세 장의 색종이가 순서대로 놓인 상태를 보여준다.그림-1여기에 그림-2에서 보인 것처럼 4번 색종이가 하나 더 놓이면 3번 색종이는 완전히 가려서 보이지 않게 된다. 그리고, 1번 색종이와 2번 색종이는 부분적으로 가려 보이며, 4번 색종이는 완전히 보이게 된다.그림-2N장의 색종이가 ..
문제출처 : https://www.acmicpc.net/problem/2839설탕 배달 성공 풀이한국어원문문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB342997970661726.013%문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해..
문제 https://www.acmicpc.net/problem/10162 문제요약 1. 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.2. 냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다.3. 우리는 A,B,C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다. 입력 : 요리시간 T(초), 출력 : A, B, C 버튼 횟수 (3개의 버튼으로 T초를 맞출 수 없으면 음수 -1..
문제 https://www.acmicpc.net/problem/10836 문제요약 1. M*M 크기의 벌집이 주어진다.2. 벌집을 나타내는 배열의 원소는 애벌레의 크기를 나타내는 데 이 애벌레들은 하루에 한번 자란다.3. 날마다 애벌레가 자라는 크기는 다르다.4. 입력으로 날마다 자라는 크기가 주어진다5. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 풀이과정 이런 문제를 많이 풀어보지 못해서 접근하는 게 힘들었다. 출력되는 수들을 잘보면 규칙을 찾을 수 있다. --> 첫 번째 열을 제외한 나머지 열들은 맨 위 원소와 값은 값을 가진다. 를 이용하여 해결했다 소스코드123456789101112131415161718192021222324252627282930313233..