아이디어!첫 두항이 0, 1이고F(n)=F(n-1)+f(n-2), 즉 이전 두 항의 합을 현재 항으로 표기해 주면 된다!적용1. 재귀(비효율적)시간 복잡도: O(N^2)중복호출이 많이 발생하기 때문에 비효율적임!#include using namespace std;long long fib(int n) { if (n > n; cout  2. dp활용시간 복잡도: O(N)dp배열에 특정 인덱스일 경우의 값을 저장해두고 사용하기!#include using namespace std;long long dp[100];long long fib(int n) { if (n > n; memset(dp, -1, sizeof(dp)); cout  3. 행렬 거듭제곱시간 복잡도: log(N)행렬과 분할정복을 이용한 거듭제곱을 활..

문제문제 설명n개의 색들이 주어지는 데 인접한 색을 동시에 사용하지 않을 려고 한다.K개의 색을 뽑는 경우의 수를 구해야 한다.최종 코드#include#define MOD 1000000003 using namespace std;int n, k;long long dp[1004][1004];int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; if (n 문제 해설dp[a][b]a: 색의 개수b: 색을 뽑는 개수dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD;색을 뽑을 때 인접한 색을 뽑을 수 없기 때문에 두 가지의 경우로 나누어 봐야 한다.1. 현제 색을 선택하는 경우: ..

문제문제 설명c와 n이 각각 주어진다.c: 모아야 하는 고객의 최소수n: 도시의 개수c명 이상의 고객을 모으기 위해서 n개의 도시에 정수배만큼을 투자하여서 최소한의 비용으로 광고를 해야 한다.ex)c=12이고, n=2이고1번 도시: 3을 투자해서 5명의 고객을 모을 수 있음2번 도시: 1을 투자해서 1명의 고객을 모을 수 있음이 경우에는 1번 도시에 6원을 투자해서 10명을 모으고, 2번 도시에 2원을 투자해서 2명을 모으는 것이 최고의 선택이다.문제 해설dp일반적으로 배낭 문제를 적용하면 다른 문제와 비슷하게 해결할 수 있다.int cost=i.first, customer=i.second; for(int j=customer;j위처럼 문제를 푼다면 쉽게 해결할 수 있다.cf) cust..

문제문제 설명괄호를 개수에 상관없이 삽입하여서 식을 최대로 만들 수 있는 경우를 구하는 것이다.숫자는 한 자리 숫자로 이루어져 있고, (+,-,*) 연산자가 있다.3+8*7-9*2식의 총길이는 19 보다 작다.문제 해설dp1. 연산괄호의 연산중에서 곱하기에서 문제가 발생하였다.(음수)*(음수)음수끼리의 연산에서 최댓값이 발생할 수도 있기 때문에 dp배열을 최솟값과 최댓값을 각각 나누어서 시행해 주었다.2. dp로직구간 dp를 활용하여서 dp탐색을 해주었다. dp [시작][끝]: 시작~끝까지의 범위에서 최댓값과 최솟값을 저장해 주었다.최종 코드#include using namespace std;int n;long long mx_dp[24][24], mn_dp[24][24];long long calculat..

문제문제 설명여기에서 n=1인 경우에는 2*2의 정사각형 하나이다.n=6인 경우에는 2*2 정사각형이 6개가 보이는 형태가 된다.그리고 두 가지 조각이 존재하는 데 조각은 서로 회전 가능하다.문제 해설여기에서 제일 중요한 n=(i-1)를 활용하여서 n=i 인 개수를 체우는 것이다.기본적으로 두개의 dp테이블을 활용하여서 결과를 도출하였다.d1: 다음과 같은 형태의 개수를 저장해 줌d2: 다음과 같은 형태의 개수를 저장해 줌그렇다면 d1, d2는 어떻게 채워야 하는지 알아보자.d1 [i]=d1 [i-1]*3+d2 [i-1]*4로 구할 수 있다.d2 [i]=d2 [i-1]+d2 [i-1]*2로 구할 수 있다.최종 코드#includeusing namespace std;const int MOD=100000000..

문제문제 설명n*m직사각형의 보드판이 존재하는 데, 다음과 같은 방법을 따른다.1. 기본적으로 가장 왼쪽 위칸, (1,1)에서 시작한다.2. 현제 위치에 있는 숫자만큼 상하좌우로 이동가능하다. 3. 만약 구덩이에 빠지면 게임은 종료한다. (이동하면서 만나는 구덩이는 무시한다.)4. 만약 무한번 움직일 수 있는 경우가 존재한다면 무조건 -1을 출력해 준다.문제 해설처음에는 bfs로도 풀 수 있을 거라고 생각하였지만 몇 가지 조건으로 인해서 어려움을 겪었다.bfs를 사용하면 방문한 점을 원복 하는 데 어려움이 존재하기 때문에 dfs, dp를 활용하여서 깊이 우선으로 탐색할 필요가 있다.dfs처음 점부터 시작하여서 깊이를 기준으로 하여서 탐색해 준다.만약 연속으로 방문하는 지점이 존재한다면 무한으로 반복된다는..