안녕하세요,
재재입니다.
BOJ 12103 짝합 수열 문제 풀이입니다.
BOJ 12103 짝합 수열
(1) 문제 설명
분류 : dyanmic proramming
출처 : https://www.acmicpc.net/problem/12103
관련 : https://www.acmicpc.net/problem/7976
$$ a_1, a_2, …, $$ 이 있을 때, $$ 1 \leq i \leq n-k+1 $$ 인 모든 정수 i에 대해서,
$$ a_i + a_{i+1} + … + a_{i+k-1} $$이 짝수라면,
이 수열은 k-짝합 수열입니다.
최소 몇개의 원소를 바꿔야 k-짝합 수열을 만들 수 있는지 구해주고,
바뀐 수열을 출력해주면 됩니다.
(2) 풀이 도출
이 문제는 두 문제로 쪼갤 수 있습니다.
- 최소 몇개의 원소가 필요한지
- 그 수열은 어떤 수열인지 (복원)
$$ (a_i + a_{i+1} + \dots + a_{i+k-1}) %2 $$ 와 $$ (a_{i+1} + a_{i+2} + \dots + a_{i+k}) %2 $$ 가 같기 위해서는,
$$ a_i % 2 $$ 와 $$ a_{i+k} % 2 $$ 가 같아야 합니다.
또한, (i%k) 번째의 원소가 홀수(짝수)인 것의 개수가 필요합니다.
이때, 상태공간은 다음과 같습니다.
dp[i][0…1] : i번째까지 계산한 값이 짝수(홀수)일 때, 바꾼 연산의 최솟값
상태공간을 활용한 점화식을 세우면 아래와 같습니다.
$$ dp[i][0] = min(dp[i-1][1] + cnt[i][0], dp[i-1][0] + cnt[i][1]) $$
dp[i-1][1] + cnt[i][0] / i-1까지 계산한 값은 홀수이고 i번째 원소들 중 짝수인 것을 홀수로 바꾸는 연산
dp[i-1][0] / i번째까지 계산한 값이 짝수일 때, 바꾼 연산의 최솟값
이때 시간 복잡도는 $$ O(N) $$ 입니다.
계산의 편의를 위해 (i%k+1) 로 계산을 하는 것이 좋습니다.
수열을 복원하기 위해서는 직전의 어떤 상태에서 왔고,
해당 번째의 숫자를 짝수(홀수)로 바꿨는지에 대한 정보를 알아야 합니다. (저장)
끝으로,
(i%k+1) 값이 1이면 k번째 원소를 의미하며,
(i%k+1) 값이 k라면 1번째 원소를 의미합니다.