아무 말

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 일단 간단하게 생각할 수 있는 점화식을 정의해 보자 D[i]는 문자열 S의 i번째 까지 고려했을 때 분할의 개수의 최솟값. 자연스럽게, if(S[i]~S[j]가 팰린드롬) D[i]=D[j-1]+1 이 성립함을 알 수 있다. 이제 매번 S[i~j]가 팰린드롬임을 어떻게 확인하냐는 건데, Manacher를 이용해도 좋지만 너무 ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 D[i]={i번째 건물을 짓는데 걸리는 총 시간} D를 위와 같이 정의 하면, 마지막으로 짓고 싶은 건물 W에서 시작하여 각 건물에 대해 건물을 짓기 위해 필요한 건물들을 짓는데에 필요한 총 시간 중 최댓값만 가져오면 됩니다. 코드 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 ..

문제링크: https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net D[i][j]={i개의 색 중, j개의 색 선택시 문제의 답} 이라고 정의하겠다. D[i][j]를 점화식으로 표현하기 위해서 case1) i번째 색을 선택한다. case2) i번째 색을 선택하지 않는다. 위와같이 케이스를 나누어서 생각했을때 D[i][j]= case1) + case2) 이다. case1) 과 case2) 를 D로 나타내면 다음과 같다. case1) D[i-2][j-1] (i번째 색을 선택했으므..

이 문제는 DP로 해결할 수 있다. 먼저 D[i][j][p]를 i~j까지의 가로등이 꺼져있고, p가 0일때 마징가는 i, p가 1일때 마징가는 j의 위치에 있는 상태에서 가로등 끄기를 시작했을때 낭비되는 최소한의 전력이라고 정의한다. 따라서 처음 시작위치는 M번째 가로등이므로 D[M][M][0] or D[M][M][1]의 값을 구해주면 된다. 수가 늘어나는 방향을 오른쪽, 그 반대방향을 왼쪽이라고 하면, 마징가가 현재위치에서 왼쪽, 오른쪽으로 이동하는 상황을 나누어 생각해주면 된다는 것을 쉽게 알 수 있다. 이를 생각하면 D[i][j][p]=min(D[i-1][j][0]+'이 경우 이동에 사용되는 전력', D[i][j+1][1]+'이 경우 이동에 사용되는 전력') 저 경우에 따른 이동에 사용되는 전력은 ..