판교의 메타몽

#include #include using namespace std; int dp[1000001]; int solve(int n){ for(int i=2; i> N; dp[1] = 0, dp[0] = 0; cout -1을 실행해서 1로 만드는 경우 : 숫자 '4'를 예시로 들어보자. '4'를 1로 만드는 방법은 나누기 2를 두번 걸치면 된다. 다른 방법으로도 1을 만들 수 있지만, 어찌되었건 공통적으로 토탈 과정은 '2'번을 거쳐서 1이 나온다. 그 다음 번째 숫자인 '5'를 1로 만든다고 가정해보자. 2를 나누냐 3을 나누냐를 떠나서, 4를 1로 만드는 과정에서 +1을 더해주면 5가 나오기 때문이다. 2. if(i%3==0) dp[i] = min(dp[i],dp[i/3]+1); ---> 3을 나누어 1..

참고 자료 : https://kwanghyuk.tistory.com/4 [백준 2579번] 계단 오르기 DP로 분류된 문제 조건 1. 계단을 오를때는 1칸 또는 2칸까지 한번에 오를수있다. 2. 연속된 3칸은 오를 수 없다. 3. 마지막 계단은 무조건 밟아야한다. 풀이 마지막 계단을 무조건 밟아야한다면 두� kwanghyuk.tistory.com #include using namespace std; int max (int a, int b){ return a>b?a:b; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int stair[301], dp[301]; int N = 0; cin >> N; for(int ..

참고 : https://lmcoa15.tistory.com/2 #include #include using namespace std; int T; int RGB[1001][3] = {0}; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; for(int i=1; i> RGB[i][0]; cin >> RGB[i][1]; cin >> RGB[i][2]; RGB[i][0] += min(RGB[i-1][1], RGB[i-1][2]); RGB[i][1] += min(RGB[i-1][0], RGB[i-1][2]); RGB[i][2] += min(RGB[i-1][0], RGB[i-1][1]); } cout

9번째 파도반(x)부터는 f(x) = f(x-5) + f(x-1)이라는 점화식을 발견했다. 쉽다고 생각해서 풀었으나 단칼에 오답이 나왔고, 아니나 다를까 타입 선언에서 흔한 실수를 저질러 버렸다 (int가 아닌 long long이어야 한다) 1. 동적할당 재귀버젼 #include using namespace std; long long arr[101] = {0,1,1,1,2,2,3,4,5}; int T; long long find(int a){ if(a8&&arr[a]) return arr[a]; else return arr[a] = find(a-1) + find(a-5); } void input(){ cin >> T; for(int i=0; i> tem; cout tem; cout

#include #define MODULE 15746 using namespace std; int arr[1000001]; int num = 0; int Find(int x){ if(x num; cout

처음 이 문제를 풀때는 재귀를 통해 풀었다. #include using namespace std; int zero=0; int one=0; void calculate (int x){ if(x==0) {zero++; return;} else if(x==1) {one++; return;} return calculate(x-2), calculate(x-1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for(int i=0; i> num; calculate(num); cout num; if(num==0) cout

동적계획법 (Dynamic Programmign) = Memoization(메모이제이션) 한줄 요약을 하자면, 기존에 구했던 답을 재활용해서 불필요한 연산은 배제하는 계산법이다. 연산의 효율성을 위해 여러 문제를 나눠서 풀고, 이 과정에서 이미 구한 답을 활용해 불필요한 계산식은 배제한다. 피보나치수열 - (일반 재귀풀이) #include using namespace std; int Fibo(int x){ int total = 0; if(x=2){ total+=Fibo(x-2)+Fibo(x-1); } return total; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; cout ..

백준 난이도별 문제 - 백트래킹의 최종문제. 그동안 풀었던 백트래킹 난이도별 문제에서 이것저것 개념을 영끌해서 풀어봤다. 실제로 각 문제들의 일부 포인트들을 차용하면 개념은 쉽게 포착할 수 있었다. 처음 만든 코드는 모든 예제에서 정답이 나왔으나, 시간초과가 나와버렸다. /* 1. 전체 수의 1/2과, 1/2~2/2까지에 해당되는 2개의 랜덤 조합을 만든다 2. 이 조합의 합산 값들의 최소값을 저장한다. */ #include #include #include #include #define MAX 20 using namespace std; int num = 0; int temp1, temp2 = 0; //임시 비교값 int minval = INT_MAX; int arr[MAX][MAX] = {0,}; boo..

문제 링크 : www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 전형적인 백 트래킹 문제. bool문으로 방문 여부를 확인하지 않고 오로지 if문을 통해 풀 수 있던 점이 편해서 좋았다. #include #include using namespace std; int n=0, mini = INT_MAX, maxi = INT_MIN, arr[12] = {0,}, pl=0, mi=0, mul=0, di=0; vo..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 스토쿠(9x9)에서 숫자를 집어 넣는데는 조건이 있다. 1. 가로 2. 세로 3. 3x3칸 이 세 가지에서 겹치는 숫자가 없어야 숫자를 넣..