백준 (206) 썸네일형 리스트형 백준 10986 - 나머지 합 https://www.acmicpc.net/problem/10986 힌트 더보기 $(A - B) \mod m = (A \mod m) - (B \mod m)$ 풀이 더보기 나머지의 성질에 대해 생각하면 $(A - B) \mod m = (A \mod m) - (B \mod m)$ 가 성립됨을 알 수 있을 것이다. 이를 문제에 적용하면 모듈러 값이 같다는 건 둘을 뺐을 때 0이 된다는 소리고 즉, pref[A] - pref[B]가 m으로 나누어진다는 것이 된다. 따라서 우리는 누적합을 계산하면서 각 나머지의 횟수를 세주고 $\binom{N}{2}$ 을 모두 계산해주면 된다. 참고로 나머지가 0인 경우는 이미 나누어진 것이므로 이거는 따로 더해주도록 한다. 물론 이항 계수의 계산에도 포함해야 한다. 전체 코드 .. [ICPC] 백준 23342 - Histogram https://www.acmicpc.net/problem/23242 서론 대회 때 누적합을 쓰는 dp겠거니 싶어서 시도해봤는데 풀지 못하고 도망쳤었다. 이번에 다른 풀이를 참조했는데 아마 대회 중에는 떠올리지 못했을 것이다. 테이블 설계 이 문제를 dp로 푸는 테이블은 다음과 같다. dp(i, j) := i번째 인덱스에서 버킷이 j개 남았을 때 분산의 최솟값 탑 다운 dp로 풀 때는 0부터 시작하는 다른 함수와 달리 n부터 시작하면서 내려가는 방식이다. 분산 구하기 중고등학교 교과 과정을 무사히 이수 했다면 모집단에서 분산을 구하는 식은 다음과 같음을 잘 알고 있다. $\sum(X - m)^{2}$ 우리는 위 분산 계산을 고속으로 하기 위해 식을 일부 전개 후 누적합을 사용할 것이다. $\sum (X^{.. [ICPC] 백준 23245 - Similarity https://www.acmicpc.net/problem/23245 대회 당시 내가 푼 문제임에도 불구하고 귀찮다는 이유로 안 쓰고 있었는데 다른 글들을 둘러보니 나와는 다른 방향으로 푼 거 같아 작성하고자 한다. 사실 여기서 적을 것은 별로 없다. 주어진 수열 쌍을 적절히 오름차순으로 정렬하고 좌표 압축을 수행하면 아래 문제와 조건이 동일해진다. https://www.acmicpc.net/problem/17409 17409번: 증가 수열의 개수 첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A1, A2, ..., AN이 주어진다. www.acmicpc.net 그러면 위 문제에서 k가 3인 버전으로 생각하고 세그먼트 트리로 LIS 카운팅 DP를 수행하면 된다. 자세한 풀이는 여기를 참고하라. 그런데 다.. 백준 14437 - 준오는 심술쟁이!! https://www.acmicpc.net/problem/14437 주어진 문자열은 사실상 장식이고 꽤 어려운 동적 계획법 문제이다. 이 포스트에서는 1차원 테이블과 슬라이딩 윈도우를 결합한 방법을 소개한다. 다음 테이블 2개를 정의한다. dp_old(i) := 이전 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수 dp(i) := 현재 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수 이미 바꾼 문자는 다시는 바꿀 수 없으므로 이전 1~25만큼 바꿨을 때 문자열이 변하는 경우를 테이블에 반영하면서 전진하면 된다. 이때 처음 dp_old(0)은 공집합 1로 규정한다. 그리고 우리는 dp를 계산해야 되는데 문제의 k가 최대 25라는 조건이 있으므로 $dp(i) =.. 백준 14848 - 정수 게임 https://www.acmicpc.net/problem/14848 포함 배제의 원리를 이용해 집합에서 원소들을 지워나가는 문제이다. 단, 이 문제는 서로 배수 관계인 수가 있을 수 있으므로 원소들을 곱할 때 최소공배수를 계산해야 올바른 답을 얻을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") .. 이전 1 2 3 4 5 6 7 ··· 42 다음
