"아직 모르겠어서 적어보는 블로깅"
문제
백준에서 13397번: 구간 나누기 2 라는 제목으로 출제된 문제가 있습니다. 구간의 합(구간의 속한 수의 총합)이 아닌 구간의 점수(구간에 속한 수의 최댓값과 최솟값의 차)를 구하는 점이 다를 뿐, 코드스테이츠의 토이 39번 문제와 기본 골격이 같은 문제라고 볼 수 있는 것 같습니다.
자연수로 이루어진 배열 K 를 n 개의 구간으로 나눌 때, 구간의 합 중에서 가장 큰 값이 최소가 되도록 하는 프로그램을 작성하시오.
위의 설명만으로는 쉽게 이해되지 않으니 예시를 하나 들어보겠습니다.
K = [1, 5, 2, 4, 1, 3, 4]
n = 3
만약 [1, 5], [2, 4], [1, 3, 4] 로 구간을 나눈다면 각 구간의 합은 6, 6, 8 가 되겠죠. 구간의 합 중에서 가장 큰 값은 8 이 될 겁니다.
만약 [1, 5], [2, 4, 1], [3, 4] 로 구간을 나눈다면 어떻게 될까요? 각 구간의 합은 6, 7, 7 이 되고 구간의 합 중에서 가장 큰 값은 7이 될 겁니다.
두 경우 중에서 구간의 합의 최대값이 더 작은 것은 두 번째 경우입니다. 가장 큰 값이 7이 되는 경우죠. 7 보다 최대값을 더 작게 만드는 경우는 없으니 7 이 우리가 원하는 답이 될 겁니다.
풀이과정 이해해가기
혹시라도 답을 기대하셨다면 죄송합니다. 레퍼런스 코드가 주어졌는데도 아직 이해하지 못해서 블로깅 해보면서 조금 더 이해해나가려고 하는 것이거든요.
아이디어 1.
K 라는 배열이 n 개의 구간으로 나뉘려면, 나뉜 구간이 가질 수 있는 최대 길이는 K 의 길이 - (n - 1) === K 의 길이 - n + 1 이 됩니다. (n - 1) 개의 구간이 최소한 한 개의 요소를 가져야 하기 때문입니다. 위의 예시에 대입해보면 7 - 3 + 1 === 5 가 되겠네요.
아이디어 2.
문제를 쪼개어보면 중복 계산이 있는 것을 발견할 수 있습니다. 구간 1 에 1 개의 값을 담고 구간 2 에 2 개의 값을 담는 것과, 구간 1 에 2 개의 값을 담고 구간 2 에 1 개의 값을 담는 경우는 서로 다른 경우이지만 마지막 구간인 구간 3 에 4 개의 값이 담기게 되기 때문입니다. 앞의 예시로 생각해보면 [1], [5, 2], [4, 1, 3, 4] 인 경우나 [1, 5], [2], [4, 1, 3, 4] 인 경우에 제일 마지막 구간의 합이 겹치는 것을 알 수 있죠.
아이디어 3.
115, 124, 133, 142, 151, 214, 223, 232, 241, 313, 322, 331, 412, 421, 511
위의 숫자들은 배열을 3개의 구간으로 나눌 때, 각 구간에 들어갈 수 있는 값의 개수를 적어본 것입니다. 115 라면 구간 1 = [1], 구간 2 = [5], 구간 3 = [2, 4, 1, 3, 4] 이런 식이 되고, 421 이라면 구간 1 = [1, 5, 2, 4], 구간 2 = [1, 3], 구간 3 = [4] 이런 식이 되겠죠.
자세히 살펴보면 일정한 공통점을 발견할 수 있을 것 같습니다.
먼저 가장 마지막 구간은 뒤에서부터 차례대로 5, 4, 3, 2, 1 의 개수 만큼 값을 가지고, 그 값은 늘 제일 마지막에서부터 시작하기 때문에 다른 변동사항이 없습니다.
두 번째 구간은 각각 1 개에서 시작해서 점차로 값을 늘려가게 되는데, 1번 구간에 따라 시작점이 바뀌게 됩니다.
첫 번째 구간은 마지막 구간과 마찬가지로 차례대로 1, 2, 3, 4, 5 의 개수 만큼 값을 가지게 됩니다. 역시 다른 변동사항이 없구요.
이렇게 적어놓고 보니 가운데 끼인 구간들을 어떻게 계산해서 비교할지가 관건이지 않을까 싶은 생각이 듭니다.
적다보니 수도코드를 적는 듯한 느낌이 되었습니다. 알고리즘이 늘 어려운 지점은 컴퓨터의 사고방식을 이해하고 맞춰가야 하기 때문인데요. 여전히 컴퓨터의 사고방식이 어렵게 느껴지는 듯 합니다. 일단 이번 알고리즘은 여기까지 해두고 추후에 더 고민해봐야할 것 같습니다.
