답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/11055 풀이 : DP문제 입니다. 가장 큰 값을 가지는 LIS가 아니라 가장 큰 값을 가지는 증가 부분 수열 이라는 점에 주의합시다. 값을 쌓아 가실 때 이전까지 증가 수열 중 현재 값과 증가 수열을 이루면서 가장 큰 값을 갖는 증가수열이 되도록 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include int n,arr[1000],cache[1000],max; int main() { scanf("%d", &n); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/16500 풀이 : DP문제입니다. 문자열을 처음부터 끝까지 훑으면서 단어들과 매칭합니다 그리고 단어 목록들로 문자열의 현재 시점까지 완성 시킬 수 있는지 없는지 여부를 word배열에 쌓아가는데, 쌓을 때 현재 검사하고있는 S문자열의 바로 앞 문자까지 완성되있는지 여부를 확인하고 완성되어 있으면 word 배열에 완성 됬다고 쌓아가시면 됩니다. 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 #include char comp[101]; char carr[101][101]; int n,word[101]; int main() { scanf("%s", comp)..

문제출저 : https://www.acmicpc.net/problem/11052 풀이 : DP문제입니다. 동전문제와 거의 일치합니다. 메모이 제이션을 할 때 현재 cache에 쌓여있는 값과 이 팩을 샀을때의 값을 비교하여 쌓아가면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n,card[1001],cache[1001]; int main() { scanf("%d", &n); for (int i = 1; i