문제해결
-
백준 17390번: 이건 꼭 풀어야 해! (입출력 관련)문제해결 2023. 11. 9. 16:40
이건 꼭 풀어야 해! 엄청 쉬운 문제인데 입출력 관련 이슈를 깨달아서 블로그 쓴다. 아래 코드로 시간초과가 나는데 30만개를 정렬만 해주는 코드가 1초가 넘을리가 없고 너무 이상했다.#include using namespace std; #define FOR(i, n) for(int i = 0; i > N >> Q; FOR(i, N) cin >> arr[i]; sort(&arr[0], &arr[N]); sum[0] = arr[0]; for(int i = 1; i < N; i++) sum[i] = sum[i - 1] + arr[i]; F..
-
백준 1882번: 분수 찾기, 30449번: Reafy 수열문제해결 2023. 11. 7. 23:59
분수 찾기 Reafy 수열 이 링크 참고해서 어거지로 풀었다.요약하자면, 이런식으로 a/b, c/d를 알 때 다음항인 p/q를 알 수 있다는 뜻이다. 이걸로 Reafy 수열은 간단하게 해결. 근데 이걸로 분수 찾기를 하려고 하니 너무 당연하게도 시간초과가 났다. Reafy 수열의 다른사람들 코드를 보니깐int find_pos(int a, int b) { int ret = 0; for(int i = 1; i > K; int a = 0, b = 1, c = 1, d = N; if (K == 1) { cout
-
백준 13908번: 비밀번호문제해결 2023. 11. 2. 00:30
브루트포스문제에 어느정도 자신감이 붙은 상태였는데 실버문제에 별안간 꺾여버렸다. 제한이 생각보다 많이 타이트했던 것... 아래 코드블럭 중 1번 코드블럭으로 아무리 제출해도 TLE가 나던데, 아무리 생각해도 실버 브루트포스문제가 이것보다 더 어려울 것 같지가 않아서 궁리를 했다. 결국 문제를 찾았는데if (!flag0) return;이자식. 이자식으로 쓸모없는 탐색을 스킵해줘야한다!if (str.find(c) == string::npos)앞으로는 그냥 깔끔하게 이걸 쓰자... string::npos 기억해두자!!#include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < int(N); i++) #define FO..
-
백준 16455번: K번째 수 찾는 함수문제해결 2023. 11. 1. 20:55
K번째 수 찾는 함수 Reafy 수열 이 문제를 풀어보려고 이것저것 찾다가 16455번까지 오게되었다. 결국 저건 카운팅 소트로 했지만... quick selection이라는 알고리즘이 존재한다더라. 이를 이용해서 빠른 시간 이내에 k번째 수를 찾는게 정답. quick selection을 대충 조사해보니 일종의 이진탐색과 비슷해보이는데 우선 아무거나 하나를 골라서, 그 수보다 작은건 왼쪽, 큰건 오른쪽에 몰아넣으며 탐색공간을 줄여나가는 것이다. 위 그림의 4번, 5번 과정if (pivval < a[lidx] && a[ridx] < pivval) { swap(a[lidx], a[ridx]); lidx++, ridx--; }코드로는 위 부분에서 조건을if (pivval
-
백준 30446번: 회문수문제해결 2023. 10. 28. 20:53
속으로 '되게 어려운데 이게 왜 실버지' 하고 꾸역꾸역 풀어서 맞췄다. 523456789의 숫자가 나오면 우선 1~9 : 9개 10~99 : 9개 100~999 : 90개 ... 이런식으로 다 더해서 99999999까지 다 처리해두고 100000000부터 523456789까지를 셈한다 그럼 여기서도 100000000부터 499999999까지는 4 * 90000 / 9이니 이만큼 더해주고 이런식으로 가운데숫자(홀수면 한자리, 짝수면 두자리)만 제외하고 남기고 다 처리해준다. 5234 5 6789. 왼쪽을 뒤집은 4325보다 오른쪽의 6789가 더 크면 추가로 5를 더해주고 만약 숫자가 523453215라 5234 5 3215 이렇게 오른쪽이 더 작으면 추가로 4만 더해준다... 암튼 이런식으로 꾸역꾸역 해..
-
백준 2749번: 피보나치 수 3 / 11444번: 피보나치 수 6문제해결 2023. 10. 26. 20:06
피보나치 수 3 피보나치 수 6 인풋이 100경이다보니깐 O(N)으로만 해도 분명히 타임아웃이 날거라고 생각했다. 100경을 다 훑을순 없고, 100만으로 나눈 나머지만 출력하라니 대충 규칙이 있겠거니 싶었다. 여러가지 숫자로 실험하며 확인해보니 어떤 숫자 M으로 나눈 나머지로 피보나치를 하면 M - 1, 1, 0, 1, 1, 2, 3, ... 이런 구간이 존재하는 듯 했다. 미리 "M - 1, 1"이 나올때까지의 피보나치 수열을 만들어 두고 Fibonacci[N % 주기]를 출력하면 끝. 끝인줄 알았는데 0ms안에 끝나는 다른 사람들 답을 보고 답을 찾아봤다. 피보나치 수를 구하는 여러가지 방법 $\begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix} = ..
-
백준 1748번: 수 이어 쓰기1문제해결 2023. 10. 25. 23:30
수 이어 쓰기1 121의 경우 한자리수가 9개 두자리수가 90개 세자리수가 121 - 100 + 1개 있을거란거 이용해서 계산해낸다.#include using namespace std; int main() { int N; cin >> N; long long ans = 0; for(int i = 0; i < int(log10(N)); i++) ans += (i + 1) * 9 * pow(10, i); ans += (int(log10(N)) + 1) * (N - pow(10, int(log10(N))) + 1); cout