폴라드 로 (2) 썸네일형 리스트형 [Python] 12070번 gNumbers (Small) / 12071번 gNumbers (Large) https://www.acmicpc.net/problem/12070https://www.acmicpc.net/problem/12071 24/05/21 스몰과 라지 풀이 방식이 거의 유사해서 같은 글로 적어보려고 한다. 문제 접근 방식: 문제 설명에 앞서서 편의 상 선공이 지는 포지션을 Cold position, 선공이 이기는 포지션을 Hot position이라고 부르겠다. 문제의 내용은 Small문제에 들어가면 wizardrabbit님이 번역해놓은 것이 있으므로 이를 참고해보자.https://www.acmicpc.net/board/view/143383 Small의 경우는 제한이 $N = 1, 000$까지이므로, DP배열을 $1,000$까지 선언하여 DP를 돌리면 된다. 이 때 어떤 숫자가 g-num.. [Python] 17633번 제곱수의 합 (More Huge) https://www.acmicpc.net/problem/17633 17633번: 제곱수의 합 (More Huge) 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 1,000,000,000,000,000,000이다. www.acmicpc.net 23/12/05 처음으로 푼 다이아3 문제이다. 높은 수학적 지식을 요구하기 때문에 사실상 혼자 이 문제를 관찰 만을 통해 풀어낸다는 건 불가능에 가깝다고 생각한다. 다만 이 문제에서 요구하는 정수론적 지식을 이미 갖추고 있는 사람이라면 다이아 3이라는 난이도에 비해 쉽게 문제를 해결할 수 있을 것이라고 생각한다. 문제 접근 방식: 먼저, 이 문제는 밀러-라빈 소수 판별법과 폴라드-로 소인수 분해 알고리즘을 구현.. 이전 1 다음