본문 바로가기

백준

 (227)
[ICPC] 백준 10266 - 시계 사진들 https://www.acmicpc.net/problem/10266 스텝 1 - 수열 정렬 시계 바늘은 모두 똑같이 생겼다. 따라서 주어진 각들을 오름차순으로 정렬해도 시계의 위상은 유지된다. 그러니까 일단 정렬하자. 스텝 2 - 각도값 보정 두 수열에 대해 맨 처음의 값이 0이 되도록 모든 원소에 적절한 값을 빼준다. 그래도 위상은 유지된다. 스텝 3 - 둘 중 하나를 두 배 하고 스트링 매칭 예제 입력 2를 보면 정렬을 함에도 절대적인 각도가 차이가 있는데 이를 해소하기 위해 수열을 복제하는 테크닉을 쓰면 정상적인 스트링 매칭이 가능하다. 이제 스트링 매치를 해서 매칭이 되면 possible, 그렇지 않으면 impossible을 출력하면 된다. 전체 코드 - kmp로 매칭했다. 더보기 1 2 3 4 ..
백준 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) =..

티스토리툴바