Diamond/Diamond IV(2)
-
BOJ 22356 - 종이, 펜, 삼각형 (Python3)
2월 12일에 SUAPC 대비를 위한 팀연습을 치뤘다. 우리 팀 중 한 명은 갑작스럽게 잡힌 일정에 대비하지 못해서 대타 버스기사 kiwiyou를 데리고 팀연습을 치루었다. 상대 팀은 전 ICPC 팀메이트였던 changhw의 팀. 진짜 강적이었다... kiwiyou가 빡구현 문제, blackstar0223이 아이디어성이 높은 그리디 문제에서 승리하지 못했으면 내가 구멍이 되었을 것이다. 난... 3문제를 풀기는 했는데 발목에 추만 달아 준 느낌이라... 셋은 UCPC 2021 예선. 내가 B, F, G를, blackstar0223이 C, D를, 그리고 kiwiyou가 A, I를 잡아내서 7문제를 풀 수 있었다. 그런데 이거 3시간 셋을 억지로 5시간으로 늘린 거라 이 멤버로 했어도 본선은 못 갔을 것 같..
2024.02.14 -
BOJ 17633 - 제곱수의 합 (More Huge) (Python3)
모든 시험이 오늘부로 종료되었다. 성적이 나온 과목은 몇 개 있는데 하나는 생각보다 덜 만족스러웠다. 어쩌겠는가, 이미 안다고 자만하며 공부를 조금 소홀히 한 내 잘못이지. 이번 문제는 정수론적 지식이 매우 강력하게 필요한, 무려 다이아몬드 IV 문제이다. 소인수분해 과정에서 밀러-라빈과 폴라드-로까지 사용해야 하는 매우 복잡한 문제. 혹시 그 쪽에 대한 지식이 필요하다면, 이 포스트를 참조하라. 심지어 이 문제를 약간 발전시킨 문제는 루비 IV에 랭크되어 있다! 그 코드도 거의 다 만들었으나, 의문의 시간초과로 인해 난항이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 ..
2022.12.21