https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 주어진 배열의 구간 합이 m으로 나누어떨어지는 경우의 수를 구하는 문제 제출하고 다른 사람들의 풀이를 보니 다들 조합으로 풀어서 신기했던 문제이다. 조합으로 푸는 방법은 생각지도 못했는데, 다른 사람들의 풀이를 보니 조합으로 접근했어도 괜찮았을 듯 싶다. 우선 배열 i ~ j의 누적 합을 구해주는데, 어차피 나머지가 중요하므로 나머지의 누적 합을 구..
math
https://www.acmicpc.net/problem/10244 10244번: 최대공약수들 n개의 수로 이루어진 수열 A가 주어질 때, 1≤lo≤hi≤n의 정의역을 가지는 함수 f(lo,hi)는 Alo부터 Ahi까지 모든 원소들의 최대공약수로 정의된다. lo와 hi는 수열의 원소가 아닌 인덱스라는 점에 주 www.acmicpc.net 구간 l ~ r 까지의 원소들의 최대공약수를 구했을 경우, 나올 수 있는 정수의 개수를 구하는 문제이다. 우선 주어지는 원소는 100 이하의 자연수이므로, 최대공약수의 개수도 최대 100개임을 알 수 있다. 하지만 i ~ n까지의 부분 집합을 하나하나 계산하기에는 시간적인 문제가 있으므로 이를 완전 탐색으로 접근하기에는 무리가 있어 보였다. 그래서 생각한 것은 1 ~ 1..
https://www.acmicpc.net/problem/19953 19953번: 영재의 산책 영재는 알고리즘 문제를 푸는 것을 좋아한다. 하지만 잘 풀지는 못하는 영재는 집중이 되지 않을 때 산책을 한다. 오늘도 집중이 되지 않아 영재는 동네를 산책한다. 영재의 동네는 2차원 좌표로 www.acmicpc.net 처음 속도 v, 방향을 바꾸었을 때 속도 변화량에 영향을 주는 요인 m , 산책 시간 t 로 이루어져있다. 일단 방향을 바꾸면 속도는 (v * m) % 10이 되는데, 곱셈의 특성상 나머지는 4번을 주기로 순환한다. 그렇기에 처음 속도를 제외한 나머지 4번의 속도 연산은 주기를 이룬다. 그러므로 t를 4로 나눈 몫은 고정으로 변하고, 나머지에 따라 최종 위치가 결정된다. 여기서 주의할 점은 v ..
https://www.acmicpc.net/problem/27856 27856번: Sum of Remainders Input consists of multiple lines. The first line contains a single decimal integer N, (1 ≤ N ≤ 100), which is the number of values of SK(n), (1 ≤ n ≤ N), that follow. The following lines contain the N values as space separated decimal integers, 10 www.acmicpc.net 자연수 n이 주어졌을 때, 1 ~ n까지의 정수를 배열 k의 원소로 나눈 나머지의 합이 Input으로 주어진다. 배열 k의 원..
https://www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 임의의 수 x, y를 잡았을 때, x%y == 0 이거나 y % x == 0이 되도록 수열 내의 원소를 바꾸어야하는데, 바꾸는 횟수가 최소가 되어야한다. 처음 접근했던 방식은 N의 범위가 1 ~ 5000이므로 반복문을 돌려 약수의 개수가 가장 많은 원소를 찾고, 해당 원소와 나누어지지 않는 원소를 바꾸는 방식이다. 그런데 코드를 돌려보니, 5 5 7 7 35 와 같은 원소가 주어졌을 때 제대로 출력이 되지 않는다는 것을 확인했고, 그래서 똑같이 반복문을 돌리되, 이번엔 약수의 개수가 아니라 나누어떨어지는 수의 개수를 구..
