꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/3012 로직 자체는 쉬운 편이였지만 끝에 다섯자리만 출력하기 위해서 모듈러 연산을 적절히 해줘야하는데 그 부분은 백준님 코드를 참고했습니다. 알고리즘은 아래와 같습니다.1. 범위 [시작, 끝]을 정해놓고 여기서 분할 탐색을 하며 적절한 쌍을 이루는지 파악합니다.2. 예를 들어 start번째 인덱스의 쌍이 i번째 인덱스라면 (start + 1) ~ (i - 1) 구간과 (i + 1) ~ end 구간을 분할 탐색해주며 쌍을 이루는지 파악합니다.3. 괄호가 명시되어있는 경우 무조건 해당 괄호랑만 쌍이지만 괄호가 명시되어있지 않고 ?라면 조커처럼 모든 경우에 대응해줄 수 있으므로 적절히 조건문을 작성해줘야합니다. #include #in..

문제 링크입니다: https://www.acmicpc.net/problem/16434 재미있는 이분 탐색 문제였습니다. high를 LLONG_MAX로 두었다가 포션 방에서 hp를 계산할 때 오버플로우가 나서 틀렸던 문제였습니다.이 부분만 조심한다면 다른 이분 탐색 문제와 유사합니다! #include #include #include using namespace std; const int MAX = 123456; int N, H; pair room[MAX]; bool func(long long mid) { long long hp = mid; long long atk = H; for (int i = 0; i < N; i++) { if (room[i].first == 1) { //몬스터보다 먼저 죽을 경우 if..

문제 링크입니다: https://www.acmicpc.net/problem/15732 이분탐색으로 접근하는데 시간이 오래걸렸던 문제였습니다.핵심은 해당 박스번호(mid) 이하에 몇 개의 도토리가 있는지를 파악하는 것이였습니다. #include #include using namespace std; const int MAX = 10000; int N, K, D; pair rule[MAX]; //해당 박스 번호가 마지막이라고 가정했을 때 몇개의 도토리가 들어있는가 bool func(int mid) { long long sum = 0; for (int i = 0; i = rule[i].first)..

문제 링크입니다: https://www.acmicpc.net/problem/5425 O(b-a) 시간복잡도는 너무 오래 걸리기 때문에 DP로 접근해야합니다.Digit DP라고 하는 다이나믹 프로그래밍 기법을 사용하면 풀 수 있는 문제였습니다.DIgit DP의 시간복잡도는 O(10 * idx * sum * tight)이기 때문에 시간 내에 충분히 풀 수 있습니다.자세한 내용은, https://www.geeksforgeeks.org/digit-dp-introduction/을 참고하시면 됩니다! 코드에 주석을 작성했기 때문에 이해가 가실 것입니다. #include #include #include #include using namespace std; long long cache[16][150][2]; //idx..

문제 링크입니다: https://www.acmicpc.net/problem/6236 전형적인 이분탐색 문제였습니다. *주의할 점은, 인출하는 양이 하루 쓸 돈보다 적으면 안된다는 점입니다. #include #include using namespace std; const int MAX = 100000; int N, M; int cash[MAX]; bool func(int mid) { int num = 1; int sum = mid; for (int i = 0; i < N; i++) { //인출하는 양이 하루 쓸 돈보다 적으면 모순 if (mid < cash[i]) return false; if (sum - cash[i] < 0) { sum = mid; num++; } sum -= cash[i]; } ret..

문제 링크입니다: https://www.acmicpc.net/problem/2343 전형적인 이분탐색 문제였습니다.high를 곡들의 길이 합으로 두고 mid를 최대 녹음 시간이라고 가정했을 때 성립하는지 여부를 판단하면 되는 문제였습니다. #include #include #include using namespace std; const int MAX = 100000; int N, M; int blueray[MAX]; bool func(int mid) { int sum = 0; //블루레이 수 int num = 1; for (int i = 0; i mid) return false; sum += blueray..

문제 링크입니다: https://www.acmicpc.net/problem/2022 코드에 앞서 func 함수를 유도하는 수식을 소개하겠습니다.$$w=w_1+w_2$$ $$h_1/w=c/w_2$$$$h_2/w=c/w_1$$$$w=w*c/h_2+w*c/h_1$$$$1=c/h_2+c/h_1$$$$1=c(h_1+h_2)/(h_1*h_2)$$$$c=(h_1*h_2)/(h_1+h_2)$$ 그리고 실수 이분탐색의 경우 정수 이분탐색과 달리 엡실론을 더해주고 빼줘야하는데 이게 참 까다롭습니다.앱실론을 너무 큰 값으로 잡으면 WA가 뜨고 너무 작게 잡으면 TLE가 발생합니다.따라서, kks227님 이분탐색을 참고하여 기존에 제가 작성하던 이분탐색 코드와는 다르게 접근했습니다. #include #include #incl..

문제 링크입니다: https://www.acmicpc.net/problem/2792 전형적인 이분 탐색 문제였습니다.해당 길이(mid)로 N명 이하의 사람들에게 나누어줄 수 있는지를 판별해주면 되는 문제였습니다. #include #include #include #include using namespace std; const int MAX = 300000; int N, M; long long jewelry[MAX]; //해당 길이로 bool func(long long mid) { long long num = 0; for (int i = 0; i < M; i++) { num += jewelry[i] / mid; if (jewelry[i] % mid) num++; } //N명 이하로 나누어줄 수 있는지 ret..

문제 링크입니다: https://www.acmicpc.net/problem/3474 간단한 수학 문제였습니다.뒤에 0이 붙는 개수는 결국 소인수분해를 했을 때 2의 개수 혹은 5의 개수 중 작은 쪽이 정합니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int t = 0; t > N; int two = 0, five = 0; for (int i = 2; i

문제 링크입니다: https://www.acmicpc.net/problem/3111 로직 자체는 백준 9935번 문자열 폭발(https://jaimemin.tistory.com/823)과 똑같은 문제였습니다.하지만 문자열의 길이가 300,000이기 때문에 O(N^2)으로는 풀 수 없는 문제였습니다.처음에는 스택으로 접근했는데 TLE가 계속 발생해서 돌핀's 님 블로그(https://dolphins-it.tistory.com/220)를 참고해 덱으로 풀 수 있었습니다. *덱이 배열처럼 인덱스 접근이 되는지 처음 알았습니다. #include #include #include #include using namespace std; const int MAX = 30000; int main(void) { ios_ba..