생각흐름
배열이 8에서 10000까지이다.
따라서 이다.
이전 결과가 중요할까?
{3, 4, 5}가 있다하고, 거기에 6을 추가한다고 했을 때,
{3, 4, 5, 6}의 난이도를 결정해야 하기 때문에 필요하다.
이전 결과가 필요 없는 방법은?
이전 결과 자체를 합치지 않으면 되지 않을까?
A라는 이전 조각에 B라는 수를 추가하는 게 아니라,
A 조각과 B라는 조각을 연결하면 된다.
이렇게 하면 A 조각의 난이도 총합과 B 조각의 난이도 총합을 더하기만 하면 된다.
여기서 눈에 띈 것이, 조각의 크기가 3부터 5까지라는 것.
즉 B의 조각은 3부터 5까지이며,
A의 조각은 B 조각의 마지막으로부터
3개 전, 4개 전, 5개 전일 것이다.
그림으로 설명하면 다음과 같다.
B 조각이 {i-2, i-1, i}가 됐을 땐 마지막이 i-3이 되는 조각의 최소 합과 더하면 된다.
아니면 {i-3, i-2, i-1, i}가 됐을 땐 마지막이 i-4가 되는 조각의 최소 합과 더하면 되고
{i-4, i-3, i-2, i-1, i}가 됐을 땐 마지막이 i-5가 되는 조각의 최소 합과 더하면 된다.
즉 i까지의 최소 난이도 합은 위 셋의 최소 값이다.
이렇게 되면 자연스럽게
dp[i] = i를 마지막으로 하는 조각들의 최소 난이도 합이 되며
dp[i] = max(dp[i-3] + class(i-2, i), dp[i-4] + class(i-3, i), dp[i-5] + class(i-4, i))이다.
다만 주의할 점은,
길이가 3 이상이어야 하므로 dp[1], dp[2]는 불가능한 값이다.
최소값 계산에 영향을 미치지 않도록 둘을 최대한 큰 값으로 설정해준다.
i=3일 때는 A조각은 사실상 없는 것이기 때문에 class(1, 3)만 필요하다.
이것을 편하게 코딩해주기 위해서 dp[0]부터는 0으로 넣어준다.
혹은 실제 코드처럼
dp를 3칸 정도 오른쪽으로 밀고
처음 세 칸을 0으로, 4, 5번째 칸을 최대값으로 하면 된다.
코드
#include <cstdio>
#include <cstring>
#include <climits>
#define MAX 10000
#define maxx(a, b) (a > b ? b : a)
#define max(a, b, c) maxx(maxx(a, b), c)
int dp[MAX + 3];
int arr[MAX + 3];
void tc();
int getDifficulty(int, int);
int main() {
int C;
scanf(" %d\n", &C);
for (int i = 0; i < C; i++) {
tc();
}
return 0;
}
void tc() {
int i = 3;
char s[MAX];
scanf(" %s", s);
int len = strlen(s);
for (; i < len + 3; ++i) {
arr[i] = s[i-3] - '0';
}
dp[3] = dp[4] = 100001;
for (int j = 5; j < i; ++j) {
dp[j] = max(dp[j-3] + getDifficulty(j-2, j),
dp[j-4] + getDifficulty(j-3, j),
dp[j-5] + getDifficulty(j-4, j));
}
printf("%d\n", dp[i-1]);
}
int getDifficulty(int s, int e) {
if (s < 3)
return INT_MAX;
int r1 = arr[s + 1] - arr[s];
int r2 = arr[s + 2] - arr[s + 1];
int difficulty;
if (r1 == r2 and r1 == 0)
difficulty = 1;
else if (r1 == r2 and (r1 == -1 or r1 == 1))
difficulty = 2;
else if (r1 == -r2)
difficulty = 4;
else if (r1 == r2)
difficulty = 5;
else
return 10;
int r = r2;
if (difficulty == 4)
r *= -1;
for (int i = s + 2; i < e; ++i) {
int newR = arr[i + 1] - arr[i];
if (newR != r)
return 10;
if (difficulty == 4)
r *= -1;
}
return difficulty;
}사실 이 문제는 다이나믹 프로그래밍하는 것이 어려운 게 아니라
입출력이랑 난이도 결정하는 부분이 더 어려웠다.
입출력은 숫자를 하나하나 받고 싶었는데 엔터나 EOF에서 끊는 코드가 전혀 먹히지 않아서
어쩔 수 없이 문자열을 받고 정수로 하나하나 저장하는 방법을 택했다.
난이도 구하는 것은 난이도 별 공차의 특징을 이용하였다.
조각의 난이도를 결정하는 것은 전체 수들의 차이다.
차가 전부 0이면 난이도는 1,
1이나 -1이면 난이도가 2,
모든 차들의 절대값은 같으면서 부호가 반대가 되면 4,
모든 차가 같을 땐 5,
이외엔 10이다.
그래서 일단 세 수를 받아서 두 개의 차를 구한다.
(조각은 무조건 길이가 3, 4, 5라서 이렇게 할 수 있도록 보장된다.)
두 개의 차가 어떤 관계를 이루냐에 따라 난이도를 일단 설정한다.
네번째 수부터 보면서 차가 기존 차와 다르면 바로 10을 리턴하고,
차가 유지되면 아까 설정했던 난이도를 리턴한다.
추가로 난이도가 4일 경우 (번갈아가며 반복)
진행될 때마다 차에 -1을 곱해준다.
