본문 바로가기

백준

 (497)
[백준 17291번] 새끼치기 (C++) 문제링크 : https://www.acmicpc.net/problem/17291#include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int dp[20];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[0] = dp[1] = 1; //초기값 for(int i=2; i 기본적으로 매년 분열하므로, dp식을 매번 직전 값에 2배를 해준다.이후 감소되는 케이스를 보면, 짝수년도 4번 분열 + 홀수년도 3번 분열이므로 사실상 짝수년도에서만 분열되었던 값들이 사라지게 되는 것을 알 수 있다. 이에 4번 ..
[백준 17391번] 무한부스터 (C++) 문제링크 : https://www.acmicpc.net/problem/17391 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, M;int arr[301][301];bool visited[301][301];int dx[] = {0, 1};int dy[] = {1, 0};void bfs(){ queue>q; q.push({0, 0, 0}); visited[0][0] = 1; while(!q.empty()) { auto [y, x, cnt] = q.front(); q.pop(); if(y == N-1 && x == M..
[백준 6571번] 피보나치 수의 개수 (python) 문제링크 : https://www.acmicpc.net/problem/6571dp = [0 for i in range(1001)]dp[1] = 1dp[2] = 2for i in range(3, 1001) : dp[i] = dp[i-1] + dp[i-2]while(True): a, b = map(int,input().split()) if a == 0 and b == 0 : break cnt = 0 for i in range(1, 1001) : if a  피보나치 계산에 따라 수가 매우 커지므로 python으로 푸는 것이 용이한 문제이다.C++로 풀 경우 문자열로 바꾸어서 계산할 필요가 있다. 이외에는 사전에 피보나치를 dp를 통해 미리 계산해놓고 입력받은..
[백준 14607번] 피자 (Large) (C++) 문제링크 : https://www.acmicpc.net/problem/14607#include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;ll N;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; cout  백준 14606번과 유사하지만 N의 범위 때문에 14606번을 풀었던 점화식을 그대로 사용한다면 메모리 초과가 발생하는 문제이다.참고링크 : https://blob-thinking.tistory.com/386 [백준 14606번] 피자 (Small) (C++)문제링크 : https://www.acmicpc.net/pr..
[백준 17265번] 나의 인생은 수학과 함께 (C++) 문제링크 : https://www.acmicpc.net/problem/17265 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N, minV = MAX, maxV = -MAX;int dx[] ={1, 0}, dy[] = {0, 1};char arr[5][5];void dfs(int y, int x, int n){ if(y==N-1 && x==N-1) { minV = min(minV, n); //최솟값, 최댓값 갱신 maxV = max(maxV, n); return; } for(int i=0; i= N || nx >= N) c..
[백준 17213번] 과일 서리 (C++) 문제링크 : https://www.acmicpc.net/problem/17213 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;ll N, M;ll dp[31][31];void func(){ dp[0][0]=1; //첫 번째 값 1 for(int i=1; i> N >> M; func(); cout  중복 조합 문제이다.간단하게 생각해보면 nHm 이지만, 모든 종류의 과일이 적어도 1개씩 있어야 한다는 조건 때문에 nHm-n이 된다.이를 조합으로 변환하여 계산을 해주면 된다.그러면 nCr = n+r-1Cr = n+m-n+1Cm-n이 된다.해당 계산은 파스칼 삼각형 공식을 ..
[백준 4097번] 수익 (C++) 문제링크 : https://www.acmicpc.net/problem/4097 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;int N;int arr[250001];int dp[250001];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); while(true) { int result = -MAX; cin >> N; if(N==0) break; for(int i=0; i> arr[i]; dp[0] = arr[0]; for(int i=1; i 구간이 비어..
[백준 16500번] 문자열 판별 (C++) 문제링크 : https://www.acmicpc.net/problem/16500 #include using namespace std;typedef long long ll;typedef pair pii;const int MAX = INT_MAX;string s;int N;string arr[101];int dp[101];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> s >> N; for(int i=0; i> arr[i]; dp[s.size()]=1; for(int i=s.size(); i>=0; i--) { for(int j=0; j 어떻게 dp 식을 세워야 하는지 감이 잘 안 잡혔던 문제이다.다른..

티스토리툴바