15824번: 너 봄에는 캡사이신이 맛있단다

먼저 해설을 보러 왔다면 여기로

힌트와 함께 해설도 자세하게 되어있다.

주안점은 풀이방식과 음수가 포함된 mod 연산

 

 

1   풀이방식

 

 

1.1   16193

 

이분야 "초초초"고수님께 양해를 구하여 풀이방식을 물어봤던 문제.

$A_i - A_j == (A_i - A_{i-1}) + (A_{i-1} - A_{i-2}) + (A_{i-2} - A_{i-3}) + \dots + (A_{j+1} - A_j)$이므로,
주어진 배열을 정렬한 배열을 B, 문제 해의 배열을 A, 임의의 정수를 $x, y, z$라 하면,
$|A_0 - A_1| + |A_1 - A_2| + \dots + |A_{n-2} - A_{n-1}| == x|B_0 - B_1| + y|B_1 - B_2| + \dots + z|B_{n-2} - B_{n-1}|$이다.

이해하기 쉽게 바꾸면, 우체국 택배가 5군데를 방문한다고 칠 때 이렇게 방문했다면,

$|A_0 - A_1| + |A_1 - A_2| + \dots + |A_{n-2} - A_{n-1}| == 2|B_0 - B_1| + 3|B_1 - B_2| + 2|B_2 - B_3| + 2|B_3 - B_4|$이라는 말.
그랬을 때 택배사는 우변의 값을 최소로 줄이려고 고민할테고, 우리는 문제에서 우변을 최대로 늘리려고 고민할 것이다.
잘 생각해보면 0부터 1은 최대 2번, 1부터 2는 최대 4번 ... 규칙을 찾을 수 있다.

 

1.2   공통점

풀이방식은 다르지만,
해결하기 위해 문제를 바꾸고, 쪼개고, 합친다는 점이 같다.

16193번은 구간으로 쪼개고 구간이 최대로 몇번 사용될지 구해서 합친다.
15824번은 최대값이 $A_i$인 조합으로 쪼개고 조합이 몇개가 있을지 구해서 합친다.

처음, 문제의 직관적으로 구하는 순서와 다르게 되지만, 결과는 같다.
그리고 논리적으로 같다는 것을 증명할 수 있다.
그리고, 바꾸는 것을 통해 컴퓨터가 해결하기 위해 필요한 순서(계산)는 줄어들게 된다.

이것이 알고리즘 외에 문제에서 원하는 능력이 아닐까.

 

 

2   음수가 포함된 mod 연산

 

설명
때문에 Python의 mod는 항상 양수, C++은 음수도 가능하다.
이것 때문에 꽤 시간을 썼는데,

for (int i{0}; i < n; i++) {
ans += ((arr[n - i - 1] - arr[i]) * p[n - i - 1]);
ans %= modifier;
}

원래 ans는 항상 양수인데 mod 후에는 양수가 아닐 수도 있다는 것!
왜냐면 ans에 더해지는 수는 처음에는 양수였다가 줄어들며 음수가 된다.
그리고 ans가 뜻하는 것이 최대 최소의 차이의 합이므로 양수여야 한다.
근데 처음에는 양수였다가 음수가 된다는 말은 "양수들의 합 > 음수들의 합"이므로,
ans는 항상 양수라는 것을 알 수 있다.

그런데 양수들의 합이 modifier를 넘어버린다면...
그래서 코드를 추가하거나 Python이었다면 자연스레 넘어갔을 것이다.

if (ans < 0) {
ans += modifier;
}

오히려 c++이었기에 자세히 알 수 있는 기회가 되어 고맙다.

 

 

ps)

처음에는 심지어 description 잘못 보고 이거 segment tree잖아? 낼름 할라다 실패.
부분 수열이 아니라 조합이다.

 

문제를 해결하며 꽤 배운 것들이 많아 재미났다.