-
[PS] 백준 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만 더해준다...
암튼 이런식으로 꾸역꾸역 해서 맞췄는데, 다른사람 답들을 보니 그냥 펠린드럼 수를 전부 다 만들어서 큰지 작은지만 봐주면 끝이였다.
생각해보면 진짜 펠린드럼수가 최대 199998개인데 이 199998개만 전부 검사해보면 되는것 아닌가.
왜 이생각을 못했을까...
숫자로 푼 버전
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast<long long>(N); i++) #define FORL(e, S) for (auto& e : S) long long n_max[10] = { 9, 9, 90, 90, 900, 900, 9000, 9000, 90000, 90000 }; int main() { long long n; cin >> n; int k = log10(n); long long ans = 0; FOR(i, k) ans += n_max[i]; int cnt = 0; FOR(i, k / 2 + 1) { int left = (n / static_cast<long long>(pow(10, k - cnt))) % 10; int right = (n / static_cast<long long>(pow(10, cnt))) % 10; if (i == k / 2) { long long a = 0, b = 0; FOR(j, k / 2) { a = ((n / static_cast<long long>((pow(10, k - j)))) % 10) * static_cast<long long>(pow(10, j)) + a; b = b * 10 + (n / static_cast<long long>((pow(10, k / 2 - j - 1)))) % 10; } if (k < 2) { if (left > right) ans += (left - 1); else ans += left; } else { if (k % 2 == 0) { if (a > b) ans += left; else ans += (left + 1); } else { int twoval = 10 * left + right; if (b >= a) { for (int i = 0; i * 10 + i <= twoval; i++) ans++; } else { for (int i = 0; i * 10 + i < twoval; i++) ans++; } } } break; } if (cnt == 0) left -= 1; ans += left * n_max[k - 2 * cnt] / 9; cnt += 1; } cout << ans << endl; }
펠린드럼 하나하나 만들어 푼 버전
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < int(N); i++) #define FORL(e, S) for (auto& e : S) #define ll long long ll odd(int num, int btw) { string left = to_string(num); string mid = to_string(btw); string right = left; reverse(right.begin(), right.end()); return stoll(left + mid + right); } ll even(int num) { string left = to_string(num); string right = left; reverse(right.begin(), right.end()); return stoll(left + right); } int main() { long long n; cin >> n; int ans = 0; for (int i = 1; i < 10; i++) if (i <= n) ans++; for (int i = 1; i < 10000; i++) FOR(j, 10) if (odd(i, j) <= n) ans++; for (int i = 1; i < 100000; i++) if (even(i) <= n) ans++; cout << ans << endl; }
'문제해결' 카테고리의 다른 글
[PS] 백준 13908번: 비밀번호 (1) 2023.11.02 [PS] 백준 16455번: K번째 수 찾는 함수 (1) 2023.11.01 [PS] 백준 2749번: 피보나치 수 3 / 11444번: 피보나치 수 6 (0) 2023.10.26 [PS] 백준 1748번: 수 이어 쓰기1 (0) 2023.10.25 [PS] 백준 23291번: 어항 정리 (0) 2023.10.25