문제 출처 : https://www.acmicpc.net/problem/2309 풀이과정 아홉명의 난쟁이 중에 진짜 난쟁이 일곱명을 추려내는 문제이다. 일곱 난쟁이의 키의 합은 100이라는 사실을 이용해 풀이하면 된다. 9명 중 2명을 선택해 난쟁이가 아니라고 생각하고 나머지 7명의 키 합이 100이면 된다.9명 중 2명을 선택하는 경우의 수가 36가지 이므로 완전 탐색으로 풀었다.코드가 더러운 것 같다. 불필요한 과정을 생각해서 코드를 깔끔하게 바꾸는 연습도 해야겠다. 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std..
문제 출처 : https://www.acmicpc.net/problem/11502 풀이과정 D[i] 를 붕어빵 i개를 팔아서 얻을 수 있는 최대 수익이라고 할 때,가능한 경우를 생각해보면 붕어빵 1개를 P[1]에 팔 경우에 남은 붕어빵의 개수는 i-1개가 되는데이 경우에 P[1]+D[i-1] 라는 생각을 할 수 있다. 하지만 D[i]는 얻을 수 있는 '최대' 수익이기 때문에 최대값만 저장해야한다. 그러므로 아래와 같은 식을 생각할 수 있다.D[i] = max(D[i],D[i-j]+P[j])이러한 식을 이용하면 쉽게 해결할 수 있다.DP문제는 많이 풀어보면 감이 온다고 했는데 점점 감이 오는거 같아 기분좋다. 소스코드 1234567891011121314151617181920212223242526272829..
문제 출처 : https://www.acmicpc.net/problem/10844 풀이과정 D[i]를 길이가 i인 수의 계단수의 개수라고 생각해보고 풀려고 하다가 시간을 엄청 날려먹었다.결국 검색을 통해 답을 보고 해결했다. D[i][j]를 길이가 i, 마지막 수가 j인 수의 계단수의 개수라고 생각하고 풀면 된다고 한다.그러면 D[i][j] = D[i-1][j-1] + D[i-1][j+1] 이라는 식이 나온다고 말한다.식만봐서는 이해하기 힘들어서 직접 길이가 3이고 마지막 수가 3인 경우를 생각해봤다.D[3][3]은 직접 경우를 따져보니 123, 323, 343, 543 총 4개였다. 이렇게 직접해보니 위의 식이 이해가 됐다. 소스코드 12345678910111213141516171819202122232..