https://www.acmicpc.net/problem/17626DP와 브루트포스를 사용하는 문제이다. 모든 수는 제곱수로 표현되기 때문에 접근을 다음과 같이 진행하였다.26일 경우는 1^2 + 25, 2^2 + 22 ...그렇게 수를 계산하면 남은 숫자 25, 22 등등이 생기는데, 그것은 다시 DP[25], DP[22] 등을 다시 진행하면 된다. 모든 제곱수를 수를 확인하였을 때, 가장 적은 수를 계속 저장하면서 값을 확인하면 된다.#include #include #include using namespace std;int main(){ vector list; int n; cin >> n; list = vector(n + 1, -1); for (int i = 1; i * i n을 입력받은 뒤, n보..

https://www.acmicpc.net/problem/11727이전 글과 마찬가지로 규칙을 찾았다. N이 1일때 1, 2일때엔 3, 3일때엔 5, 4일때엔 11..짝수일 때에는 전 수의 2배 + 1, 홀수일 때에는 전 수의 2배 - 1로 되어 이 식을 적용하였다.#include #include using namespace std;int main(){ vector list; int n; cin >> n; list.push_back(0); list.push_back(1); for (int i = 2; i

https://www.acmicpc.net/problem/11726규칙을 찾아내면 된다. N이 1일 때엔 방법이 한 개. N이 2일 때엔 방법이 2개, N이 3일 때엔 방법이 3개 ....좀 진행해보면 이전 두 수를 더한 값이 정답이라는 것을 알 수 있다.#include #include using namespace std;int solve(int N){ vector list = vector(1001, -1); list[1] = 1; list[2] = 2; for (int i = 3; i > N; cout

https://www.acmicpc.net/problem/9095DP는 점화식. 1과 2, 3으로 구성되어 나타내는 방법을 구하는 문제이다.점화식을 생각해 내는 것이 어렵지만 1, 2, 3을 사용하는 점을 생각하여 도출해 내야 한다.#include #include using namespace std;vector answer = vector(12, -1);void cal(){ answer[1] = 1; answer[2] = 2; answer[3] = 4; for (int i = 4; i > T; cal(); for (int i = 0; i > input; cout 하나의 수에 대해 방법을 구할 때에 처음에 1이 오게 되면, 남은 숫자는 N - 1의 방법 합이 된다.2가 오게 되면, 남은 숫자는 N - 2..

https://www.acmicpc.net/problem/2579다이나믹 프로그래밍을 이용해서 풀어야 하는 문제이다. #include #include using namespace std;vector stair;vector answer;int num;void init(){ cin >> num; answer = vector(num + 1, -1); stair = vector(num + 1, -1); for (int i = 1; i > temp; stair[i] = temp; }}void solve(){ answer[1] = stair[1]; answer[2] = answer[1] + stair[2]; answer[3] = max(stair[1] + stair[3], stair[2] + stair[3]); ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 (DP)와 브루트포스 알고리즘을 활용한 문제이다. 주어진 기간 안에 최대한의 이득을 확인하는 문제이기 때문에 점화식으로 계산하여, DP리스트에 그 날에 할 수 있는 최댓값을 넣어주면서 진행하면 된다. N날이 되었을 때 DP[N]에 있는 값이 그 기간 안에 할 수 있는 최대의 가치를 가진 일이 될 것이다. #include using namespace std; int N; int list[15][2]; int dp[15]; int main() { ios::sync_with_stdio(0); cin.tie(0); cou..