MingyuPark

문제 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 아이디어 페르마의 소정리를 이용해서 풀 수 있다. 어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 $a \times b^{-1} \text{mod X}$ (X는 소수)으로 대신 계산하도록 한다. 여기서 $b^{-1}$ 은 b의 모듈러 곱셈에 대한 역원이다. m이 소수이기 때문에 b의 모듈러 곱셈에 대한 역원은 $b^{m-2} \text{mod m}$이 된다. 이를 f 라는 함수를 이용해서 계산한다. operation 함수를 이용해서 ..

문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아이디어 누적합을 이용해야 한다. 주어진 표에서 각 좌표별로 누적합을 계산한 뒤에 내가 구하고자 하는 좌표의 누적합을 구하면 된다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 위의 표에서 각 위치별 누적합을 구해보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 우선 첫 번째로 (1, 2)의 2에 (1, 1)의 1을 더해주..

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어 https://park-mingyu.tistory.com/38 [백준 1629] 곱셈 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어 $f(n)$을 $x^n$을 계산하 park-mingy..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어 $f(n)$을 $x^n$을 계산하기 위해 필요한 최소 계산 횟수라고 하자. $2^16$을 계산하기 위해 필요한 최소 계산 횟수를 구해보자. 직접 계산하면 2를 16번 곱해야 하기 때문에 16번의 계산이 필요하다. 이 경우 n이 2,147,483,647이 되면 계산 횟수가 너무 많아진다. 이럴 때 분할 정복을 이용한다. $f(16)$ = $f(8)+1$ : $2^{16} = 2^8 * 2^8$이기 때문 $f(8)$ = $f(4)+1$ : $2^{8}..

문제 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 아이디어 단순히 문자열을 슬라이싱하면 되는 문제이다. 0번 인덱스에서 시작해서 글자수를 늘려가면서 슬라이싱한 후 lst에 저장한다. 문자열 s를 s = 'hello'라고 해보자. 0번 인덱스에서 탐색한 부분 문자열은 h, he, hel, hell, hello 가 된다. 1번 인덱스에서 탐색한 부분 문자열은 e, el, ell, ello 가 된다. ... 4번 인덱스에서 탐색한 부분 문자열은 o 하나밖에 존재하지 않는다. 즉, 우리가 고려해야 하는 값은 시작 인..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 아이디어 가장 위층부터 아래층에 있는 두 수 중 하나를 선택해서 가장 아래층으로 가는 경로 중에서 합이 가장 큰 경우를 구하는 문제다. 문제 예제에서 최적의 경로부터 보면 다음과 같다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 쉽게 생각하면, 가장 위층부터 시작해서 아래층으로 내려가면서 합을 구해보면 된다. 5층의 경우 양쪽으로 갈 수 있기 때문에 4층에 더해주면 다음과 같이 10, 15가 된다. 또한 각 층의 가장 왼쪽은 그 윗층의 가장 왼쪽값만 더..