[백준] 2003번 수들의 합 2 [Python] - 누적 합
N개의 수열과 자연수 M이 주어지면, i번째 수 부터 j번째 수 까지의 합이 M이 되는 경우의 수를 구하는 문제 더보기 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N$(1 ≤ N ≤ 10,000)$, M$(1 ≤ M ≤ 300,000,000)$이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. https://www.acmicpc.net/problem/2003 수열을 ..
[백준] 11660번 구간 합 구하기 5 [Python] - 다이나믹, 누적 합
N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 문제. $(x, y)$는 x행 y열을 의미한다. 1차원 수열의 구간 합 문제 https://savvy0402.tistory.com/216 위 문제와 비슷하지만 이번에는 2차원 수열의 구간 합을 구하는 문제라고 보면 된다. 더보기 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 프로그램을 작성하시오. $(x, y)$는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 $(2, 2)$부터 $(3, 4)$까지 합을 구하면 3..
[백준] 1629번 곱셈 [Python]
$A^{B} \,\%\, C \,=\, ?$ A, B, C 가 주어졌을 때 위 식의 답을 구하는 문제 더보기 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. https://www.acmicpc.net/problem/1932 분할 정복을 이용한 거듭 제곱 B가 2의 거듭제곱일 경우 재귀적으로 A의 제곱을 반복해서 너무 큰 지수 연산을 피한다. B가 홀수 일때, $($B-1$)$의 절반에 대해서 위의 과정이 가..
[백준] 1149번 RGB거리 [Python] - 다이나믹
N개의 집이 일렬로 있고, 빨강, 초록, 파랑 이 세가지로 칠하는 경우 각각 집마다 색마다 비용이 주어졌다. N은 2 이상 1000이하이고, 비용은 1000 이하 자연수이다. 이웃 집과 다른 색으로 N개의 집을 모두 색칠할 때, 비용 합산의 최솟값을 구하는 문제 더보기 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i$(2 ≤ i ≤ N-1)$번 집..
