수학22 백준 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번: 잘 알려진 합 구하기 주어진 수식의 값을 1000000007로 나눈 나머지를 출력한다. 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. 백준 25339 / C++ https://www.acmicpc.net/problem/25339 25339번: 반전 수와 쿼리 1부터 N까지의 수가 한 번씩 등장하는 수열 P={1,2,⋯,N}이 주어진다. 수열 P에 대해, iPj를 만족하는 순서쌍 (i,j)의 개수를 P의 반전 수라고 정의하자. 이 www.acmicpc.net 쿼리마다 반전수의 홀짝성을 확인해주는 문제이다. 수학이 전부인 문제. [ 풀이 ] // 1번 쿼리의 경우 Ai와 Aj를 교환한다고 하자. Ai와 Aj 사이의 수열에만 관심이 있다. 나머지 A1~Ai-1, Aj+1~An은 Ai와 Aj가 교환되도 반전수에 영향이 없다. Ai+1~Aj-1중 Ai와 반전쌍을 이루는 것의.. 2022. 7. 12. 백준 1111 / C++ https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 수열이 규칙성을 만족하는지 확인하고 유일하면 출력까지 하는 문제이다. 일단 규칙이 p*전항+q 이므로 미지수가 2개이다. 따라서 a1, a2, a3만으로 p와 q는 결정된다. (항이 3개 이상일때) // 항이 3개 이상 p=(a3-a2)/(a2-a1)이 된다. p가 정수면, q도 정수이므로 a3-a2가 a2-a1의 배수인지만 체크해주자. (예외처리는 a1=a2일때) 이렇게 해서 정수 p, q를 찾았다. 이제 수열을 1번 돌면서 모두 이 규칙인지 확인한다. 잘 가다.. 2022. 7. 9. 이전 1 2 3 4 5 6 다음