2. 28

• 방학이 끝나가기 전에 <Transistor>를 클리어했다. 만원정도 주고 산 것 같은데 17시간정도 재밌게 플레이했음.. RPG는 정말 다양한 실험이 가능한 장르고 게임의 꽃이라고 불려도 될 것 같다ㅠㅠ
• BOJ 1416 <팬서비스>는 symmetry를 잘 활용해야 하는 DP문제. 길이가 2*K인 쿠폰번호가 있고, 다음 두 조건 중 하나를 만족하는 가짓수를 세는 것이다. (1) 첫 K개 합 = 마지막 K개 합 (2) 짝수번째 합 = 홀수번째 합. 합집합이므로 각각의 집합을 A, B로 두면 \( n(A) + n(B) - n(A \cap B) \)를 세면 되는데, \(A, B\)의 집합은 쉽게 서로를 일대일대응 시키는 변환을 찾을 수 있다. 고로 \(n(A) = n(B)\)이다.
• 이제 \(n(A \cap B) \)를 세야 하는데, DP로 반을 나눈 K개의 일련번호상에서 전체합이 \(i\)고 짝수합이 \(j\)인 집합의 개수를 셀 수 있다. 이를 \(d[i][j]\)로 두면 이제 구하려는 값은 K가 짝수인지, 홀수인지에 따라 다르게 구해진다. 짝수일 경우 \(d[i][j] * d[i][i-j]\)를 모두 더하고, 홀수인 경우 \(d[i][j] * d[i][j]\)를 모두 더하면 된다. 짝수인 경우 직관적이나 K가 홀수의 경우엔 마지막 K개를 뒤집는 변환을 해버리는 셈이다.