처음에는 단순한 스위핑 알고리즘인줄 알았다. 각각의 높이에서 가장 높은수와 낮은 수의 값이 17이 넘어가면, 이들은 1씩 더하거나 빼서 차이를 17로 만들고, 17이 만들어졌을때 가장 낮은 수만큼 더해진 결과값을 채택하는식으로 했다.
그러나 이럴경우 매번 앞뒤를 1씩 더하는 반복문이 너무 지저분했고, 치명적인 반려또한 존재했다.
예를들어 N = 3와 [1, 5, 20]을 입력했을때, 정답은 1과 20을 각각 한칸씩 줄여서 1 + 1 = 2로 2가 출력되어야하는데, 내 알고리즘 같은 경우는 가장 낮은수를 먼저 움직여보고, 그 다음에 가장 높은수를 낮추는 식으로해서, 우선 17이 되거나 내 앞에있는 다음수, 그러니까 지금같은경우는 1이 5가 될때가지 1을 더하는 방식으로 진행하기 때문에, 1을 2칸 움직여서 3이되고, 20(최대값) - 3(최소값) = 17 조건이 성립되기때문에 정답이 2^2 = 4가 되는 문제가 있었다.
알고리즘 분류를 보니 브루트포스로 분류되어있어서 생각해보니, 언덕의 수는 1000개가 최대지만, 높이는 최대가 100이였다. 즉 가장 낮은건 0에 가장 높은게 100이니까 반복문을 돌면서 0 부터 100까지 있는 17의 차이가 나는 구간을 만들고, 입력받은 모든 언덕들을 이 구간에 넣으려고 했을때 더해지거나 빼지는 값들의 합이 가장 낮은수를 찾는 방식으로 바꿔보았다.
[0, 17], [1, 18], [2,19] ..... [83, 100] 이런식으로 말이다. (모든 숫자를 이러한 범위로 만들어 넣으면 최소값과 최대값 차이가 17이니까)
예시를 들자면
입력)
N = 3
[1, 5, 20]
for문을 이용해서 j = 0 부터 83까지의 수에 + 17의 해서 구간을 만들고 [1, 5, 20]과 비교한다. 이때 j는 범위는 최소값, j + 17은 범위의 최대값이다.
if (farm[i] < j) 현재 언덕이 범위의 최소값보다 낮으면 j - farm[i]를 해서 언덕의 최소범위로 높혀준다.
if (farm[i] > j + 17) 현재 언덕이 범위의 최대값보다 높으면 farm[i] - ( j + 17)을 해서 언덕의 최대범위로 낮춰준다.
언덕이 범위의 안에 있을경우 해당 언덕의 값을 변경할 필요가 없으므로 위에 두개의 if문에 포함되지 않는다.
위의 예시로 다시 돌아가보면
j = 0부터 시작하고 j < 83에 j++일때
[0, 17]일경우 1, 5는 0 부터 17에 포함이 되서 따로 계산하지않는다. 20은 범위최대값인 17보다 3 크기때문에 3^3이 해당 범위에 대한 값이다.
그 다음범위인 [1, 18]도 마찬가지로 1, 5는 건너뛰고, 20 - 2 = 18이기때문에 값은 2^2이다. 이전에 있던 값과 비교했을때 더 작은수이기 때문에 이를 채택해준다.
[2, 19]일때 범위최소값인 2는 1보다 크기때문에 1을 우선 더해준다. 5는 범위안의 숫자이기때문에 스킵하고, 20은 범위최대값인19보다 1크기때문에 최종값은 (1^1) + (1^1) = 2이다. 전에 가지고있던 최종값과 비교해서 더 작은수이기에 채택해준다.
이런식으로 쭉쭉 돌아서 [83,100]까지 돌고 가지고있는 가장 작은 최종값이 정답이 되는것이다.
결국은 어떠한 수가 언덕값으로 들어오든, 한정된 범위만 만들어서 비교하면 되는 문제였다.
'알고리즘' 카테고리의 다른 글
| 백준 [14888] - 연산자 끼워넣기 (0) | 2024.12.15 |
|---|
