algorithm

https://www.acmicpc.net/problem/1437풀이가 2가지가 있다.1. Dp2. 수학1. 다이나믹 프로그래밍Dp로 풀려고 하면 당연히 점화식을 찾아야 하고 노가다를 하다보면 점화식이 쉽게 찾아진다.n > 4인 경우에서 dp[n] = dp[n-3]*3이 된다. #include #define mod 10007using namespace std;int main() { int n; cin >> n; int* arr = new int[n+1]; arr[0] = 0; arr[1] = 1; arr[2] = 2; arr[3] = 3; arr[4] = 4; for(int i = 5; i  2. 수학수학적 접근이 쉽지 않은데... 결론적으로는 3을 가장 많이 만들면 된다.DP로 접근할때 노가다한 수들을..

https://www.acmicpc.net/problem/28703maxPq, minPq 우선순위 큐 2개를 이용해서 하나씩 뽑으면서 차이의 최솟값을 갱신해나가면 된다.문제는 위의 과정의 종료조건인데, 구해야 하는 것이 최대값-최솟값의 차이기 때문에 만약 입력으로 주어지는 모든 수를 2배를 할 필요가 없다. 모든수가 2배가 되면 1/2배를 할 수 있고 그럼 2배가 된 상태보다 차이도 1/2이 되므로 모든 수가 2배이상으로 커지는 것은 의미가 없다.따라서 모든 수가 2배가 되기 전까지가 반복문의 종료조건이 된다. #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, num;..

https://www.acmicpc.net/problem/20302입력받는 모든 수를 소인수 분해 해서 곱셈과 나눗셈으로 나눠주면 된다.곱셈일 때는 등장하는 소수의 개수만큼 배열에서 더해주고, 나눗셈일 때는 반대로 빼주면 된다.최종 배열을 탐색하면서 0보다 작은 값이 있으면 분모에 해당 소인수가 살아있다는 뜻이므로 결과가 유리수가 된다.소인수분해하는 코드를 알아가기 좋은 문제다. #include #include #include #include #define endl "\n"using namespace std;int n, num;vector arr(100001,0);void fac(int a, bool check){ int tmp = sqrt(a); if(check){ for(int i = 2; i 1..

https://www.acmicpc.net/problem/2048노가다를 좀 하다가 맞을 거 같아서 찍었다...찍었다고 말하긴 했지만 사실상 수학적 직관력이 필요한 문제아몰랑 노가다의 결과는 r >= 4이면, 마지막에 붙인 수를 2로 r만큼 나누면 홀수가 된다. 따라서 r >= 4 일때는 r이 답이고, 다른 경우에는 수가 작으니 직접 다 붙여서 2로 몇번이나 나눠지는지 직접 나눠보면 된다. #include #include #include #define endl "\n"using namespace std;int t,l,r;int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> t; while(t--){ cin >> l ..

https://www.acmicpc.net/problem/12923좀 애먹은 문제다. 문제에서 주어지는 테스트 케이스가 간단해서 그런지 반례 상황을 생각못하고 여러번 틀리면서 찾았다. 문제는 최소 클리어 횟수를 사용해서 스테이지의 모든 별들을 모으는 코드를 작성하라는 것이다.아마 대부분 b를 오름차순으로 정렬해서 작은 b부터 얻을 수 있는 별들을 다 얻고 부족하면 먹을 수 있는 a로 별을 얻어서 b를 채우는 식으로 풀면 되겠다고 생각할 것이다.하지만 a로 별을 얻을 때 어떤 스테이지 부터 먹어야 하는지 고민이 될 것이다. 코드는 다음과 같다.#include #include #include #define pii pair#define INF 1000000000using namespace std;bool co..

https://www.acmicpc.net/problem/25116수영이가 쿠키런 맵을 만들고 싶고, 스테이지 난이도 수열이 주어진다.● 한 맵에는 여러개의 스테이지가 있으며 연속적인 스테이지 난이도의 합이 M보다는 커야 한다.● 난이도 합이 M보다는 커지는 연속적인 스테이지 구간이 K개 이상 존재해야 한다.● 스테이지 난이도 수열의 난이도를 모두 X만큼 증가시킬 수 있다.이때 스테이지 조건을 만족하는 가장 작은 X를 구하라는 문제다. 다음과 같은 문제는 X에 값을 대입해보면서 스테이지 조건을 만족하는 경우 중 최소값을 찾아야 한다.이때 대입하는 방식이 이분탐색을 통해 정답 범위를 점점 좁혀가면서 X값을 찾아낼 수 있다.따라서 작성해야할 코드는 1. 이분탐색 코드2. 이분탐색 안에 스테이지 조건은 만족하..