수학20 백준 14958 / C++ https://www.acmicpc.net/problem/14958 14958번: Rock Paper Scissors There is a Rock Paper Scissors (RPS) machine which generates Rock, Paper, or Scissors randomly. You also have a similar small Rock Paper Scissors machine. Before the game, the RPS machine will generate a list of its choice of Rock, Paper, or Scissors of th www.acmicpc.net [ 풀이 ] 매번 옮겨가면서 계산하면 O(mn)이다. FFT로 합성곱 구하는 과정을 NlogN에 해주자. .. 2022. 8. 22. 백준 11616 / C++ https://www.acmicpc.net/problem/11616 11616번: Digit Division We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m. Find the number of different suc www.acmicpc.net [ 풀이 ] 우선 짚고갈 것은 전체수가 m의 배수가 아니라면 m의 배수인 여러부분으로 분할할 수 없다. 이제 전체수.. 2022. 8. 12. 백준 21761 / C++ https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net [ 풀이 ] 부피 ABCD에서 한 변을 증가시키면 (A+U)BCD가 된다. 그럼 매번 변화시키면서 1+U/A가 커지도록 해주면 된다. 그리디하게 매번 A,B,C,D중 제일 큰 U를 뽑아서 1+U/x가 제일 큰걸 매번 뽑아주면 된다. 기존 ABCD에서 이렇게 가장 큰 비율을 매번 곱해줘야 최대가 되는건 자명하다. 그 비율이 1보다 크기 때문에 항상 값이 커지기 때문이다. 매번 제일 큰 .. 2022. 8. 8. 백준 24518 / C++ https://www.acmicpc.net/problem/24518 24518번: 잘 알려진 합 구하기 주어진 수식의 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net [ 풀이 ] 몫이라는게 N에 가까워질수록 같은값이 점점 많아진다. 같은값이 나오는 구간을 묶어보자. [N/2+1, N] 은 몫이 모두 1이다. [N/3+1, N/2]은 몫이 모두 2이다. 이렇게 구간 나누는걸 sqrt(N)이 나올때까지 한다. 이제 sqrt(N)까진 그냥 f(i)g(i)를 계산하고 나머지 구간들은 몫이 같은 구간마다 나머지들을 곱해서 더해준다. 여기서 그냥 훑으면서 계산하면 O(N)이다. 나머지는 0, 1, ...., m-1이 반복된다는 성질을 통해, 구간마다 주기를 찾고 잘 처.. 2022. 8. 1. 이전 1 2 3 4 5 다음