노는 게 제일 좋아

우선 숫자가 큰 문제이다. 뭔가 크다. 어렵진 않았지만.. 그냥 오랜만에 푸니까 감이 안왔다. https://www.acmicpc.net/problem/2805 시간초과 될 것을 알면서도 brute force로 해봤다. #include using namespace std; int N,M; int maxi = 0; int sum; int arr[1000001]; int main(){ cin >> N >> M; for(int i = 1; i> a; arr[i] = a; if(a>=maxi){ maxi = a; } } maxi--; while(1){ sum = 0; for(int j = 1; j0) sum += temp; } if(sum>=M){ break; } maxi--; } cout > N >> M; f..

어렵다기보다.. 수학으로 풀면 규칙 찾아내는 것이지만 다이나믹 프로그래밍 분류에 있어서 뭐 그렇게 풀려고 했으나..내 머리가 모자라서.. https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 우선 다이나믹프로그래밍으로 풀려고하는 방법은 큰 문제를 작은 문제로 쪼개는 것이다. 때문에 x부터 y라면 x 부터 y-1까지 가는 방법에서 y-1에 2로 도착하는 방법과 y-1에 1로 도착하는 방법이 있으니 이것을 잘..

어렵지 않지만.. 헷갈렸다. 행과 열을 바꿔서 해버렸따.. https://www.acmicpc.net/problem/2225 #나의 풀이 #include #define MAX 1000000000 using namespace std; int N, K; long long dp[201][201]; // N, K int main() { int i, j, k; cin >> N >> K; //하나를 선택할 때는 무조건 하나를 선택함. for (i = 0; i

어려웠다. 부분으로 쪼갤 수 있었지만 생각이 잘 안났다. https://www.acmicpc.net/problem/9251 모든 부분을 부분수열로 쪼개보니.. for문이 3개나 나와서 그냥 떄려쳤다. DP문제라는 것을 한 번에 파악할 수 있었다. 어떻게 전체 문제를 부분으로 쪼갤 수 있을까 고민했다. 처음에는 맨앞에서부터 접근했지만 틀린 접근법이었다. 마지막부터 조사했어야 했다. 길이가 L1, L2의 문자열이 있다. 만약 마지막 부분이 같다면 해당 마지막부분을 제외한 채로 나머지 L1 -1 , L2 - 1의 문자열의 가장 긴부분을 조사하면 될 터였다. 마지막 부분이 다르다면 둘 다 제외하는 것이 아닌 L1 - 1, L2 또는 L1, L2 - 1의 문자열을 조사하면되었다. 그리고 문자열이 비어있는 것과의 ..

바로 생각한 대로 실행하면 되는 문제다. https://www.acmicpc.net/problem/2003 우선 N~M번째 까지의 합은 1~M - 1~N-1 인것을 나는 이용했다. 하지만 이제부터는 잘한 사람들에게서도 나와 무엇이 다른지 공부하기로 했다 우선 나의 풀이를 보고 다른 잘한 사람들의 풀이를 비교해보자 #맞은 풀이 #include using namespace std; int N,M; int arr[10001]; int dp[10001]; // dp[i] -> 1~i번째까지의 합 // N~M 까지의 합은 1~M번째 까지의 합 - 1~N-1 번째까지의 합. int main(){ cin >> N >> M; int cnt = 0; for(int i=1; i> arr[i]; dp[i] = dp[i-1]..

전형적인 DP문제다. 처음엔 백트래킹으로 풀려했으나.. 개수가..너무 많아서 백트래킹을 어떻게 캐시로 저장할까하다가.. 방향을 틀었다. https://www.acmicpc.net/problem/11052 #처음 틀린풀이 #include using namespace std; int N; int card[1001]; int dp[1005][1005]; //카드를 살 때, 카드 수는 적되 가격은 높게 사야한다. //현재 카드가 i개 가지고 있고 카드의 수와 가격을 보면서 골라야 한다. //결국 다 뒤져봐야함 int M = -1; //최댓값 int x = 0; int func(int cnt, int val){ if(dp[cnt][x] > 0) return dp[cnt][x]; //종료조건 if(cnt > N)r..

음 아주 어렵진 않지만 생각하기 어려운 문제다. https://www.acmicpc.net/problem/12865 #맞은 풀이 #include using namespace std; //가장 가치가 크게 해야함. 가장 큰 무게가 가장 큰 가치를 보장하지 않음 //모든 것을 보고 넣을 지 말 지 정해야 함. (Brute Force지만).. 정말 다조사하면 시간초과남 //똑똑하게 조사해야함. 2^100 연산이 필요. 캐싱 필요( 값 저장) // 담을 수 있는지, 없는지 // 담을 수 있다면 담는 것이 좋은지, 아닌지 int weight[101]; // 무게 int value[101]; // 가치 int N,M; // 개수, 최대무게 int dp[102][100001]; // 값 저장 //재귀를 이용한 풀이 ..

DP의 전형적인 문제지만 DP의 과정도 출력한다고 해서.. 조금 출력을 고려해야하는 문제다. https://www.acmicpc.net/problem/12852 #처음 맞는 풀이 - 수정 전 #include using namespace std; int dp[1000001]; int num; int main(){ cin >> num; dp[1] = 0; dp[2] = 1; for(int i=3; i

이것도 DP의 예로 입력이 많고 테스트 케이스도 많아서 DP 풀어야 하는 방식과 비슷할 거라고 예상하고 들어갔다. https://www.acmicpc.net/problem/11659 #맞은 풀이 #include using namespace std; int N,M; int map[100001]; int dp[100001]; int main(){ ios :: sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i = 1; i> a; map[i] = a; dp[i] = a+dp[i-1]; } while(M--){ int a,b; cin >> a >> b; cout

하.. 이건 방법은 알았지만 구현이 잘못되어서 시간이 오래걸렸다. https://www.acmicpc.net/problem/10844 #맞는 풀이 #include #define X 1000000000 using namespace std; int N; long long dp[101][10]; int main(){ cin >> N; dp[1][0] = 0; for(int i = 1; i N; int sum = 0; for(int i = 1; i