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. 이분탐색 안에 스테이지 조건은 만족하..

https://www.acmicpc.net/problem/30805수열 A와 수열 B에서 공통으로 가장 큰 수를 찾고 그 수를 ans벡터에 넣어주는 식으로 최대 공통 수열을 찾았다.여기서 수열 A와 B의 공통으로 가장 큰 수를 찾았으면 각 수열에서 공통으로 가장 큰 수의 인덱스보다 작은 인덱스 숫자들은 최대 공통 부분 수열의 원소가 될 수 없으므로 pop해준다.위의 방식을 한쪽 수열의 벡터의 크기가 0이 될때까지 반복한다. 그럼 최종 ans벡터 수열이 사전 순 최대 공통 부분 수열이 된다. #include #include #include #define endl "\n"using namespace std;int main() { int n,m,num; vector a; vector b; cin >> n; f..

https://www.acmicpc.net/problem/12020 요즘 선형대수학을 공부하고 있는데 백준에 예제가 잘 나와있어서 연습하기 참 좋다.어떤 행렬 A를 하삼각행렬과 상삼각행렬로 분해하는 과정이다.Ax = b 라는 선형연립방정식을 풀 때 단순히 가우스 소거법을 이용하여 풀어도 되지만, LU분해를 사용하면 훨씬 효율적으로 계산할 수 있다. 가우스 소거법을 활용한 선형연립방정식의 Time complexity: N³LU분해를 활용한 선형연립방정식의 Time complexity: N²  LU분해를 하는 과정에서 가우스 소거법이 필요해서 최초의 분해를 하는 데에는 N³의 시간복잡도를 필요로 하지만, 분해는 한번 해 놓으면 다시 할 필요가 없다는 점에서 이득을 볼 수 있다. 한마디로 Ax = b에서 b가..

https://www.acmicpc.net/problem/27977 27977번: 킥보드로 등교하기 첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개 www.acmicpc.net #include using namespace std; int l,n,k,diff = -1; int arr[100002]; int main() { cin >> l >> n >> k; arr[0] = 0, arr[n+1] = l; for(int i = 1; i > arr[i]; } for(int i = 1; i