어흥

문제 링크: https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 1. 주의할 점 - 분할정복 + 세그먼트 트리를 통해 해결한다 2. 구현 - 직사각형의 높이에 대한 정보를 Arr[] 배열에 담는다 - Tree[] 배열을 동적할당한다 - Init() 배열을 통해 Tree[] 배열에 최소 높이를 가지는 인덱스 번호를 저장한다 - findMinIdx() 함수를 통해 Left~Right까지의 Arr..

문제 링크: https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - 계산을 진행할 때 마다 MOD연산을 해줘야한다 - TLE를 막기 위해 Pow함수를 직접 구현해줘야 한다 - 페르마의 소정리에 대해 알고 있어야 한다. 2. 구현 - 페르마의 소정리를 이용한다 Ex) (A!/B!) % MOD ->(A! * Pow(B,MOD-2)) % MOD로 바뀐다 - Pow 함수는 분할정복을 이용해서 해결한다. Idx가 0과 1일 때를 제외하곤 Idx가 짝수면 {Pow(..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGKdbqczEDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 페르마의 소정리를 이용해서 풀어야 한다. - Pow연산시 분할정복을 이용해야 시간초과가 발생하지 않는다 2. 구현 - nCr = (n)!/{(n-r)!*(r!)}이 성립하며, 각 숫자에 대한 팩토리얼%MOD의 값은 미리 구해놓는다 -> 시간절약 - nCr % MOD = up/down의 식으로 바꾼다. up = n!%MOD, down = {(n-r)!%MOD *(r!)..