12026번 BOJ 거리

문제 설명

이번 문제는 B, O, J 중 한 문자로 이루어진 타일에서 아래 규칙대로 걸을 경우 필요한 에너지의 양의 최소값을 구하는 문제입니다.

• 보도블럭을 밟는 순서는 B, O, J, B, O, J ... 순서대로 걷게 된다.
• i에서 k 타일로 이동하는데 필요한 에너지는 (k-i)^2이다.
• 첫 번째 타일은 무조건 B이고, 마지막 타일에 무조건 도착해야 한다. (마지막 타일에 도착할 수 없을 경우 -1을 출력)

 

 

문제 풀이

아이디어

1.

우선 문제의 조건을 살펴봐야 합니다. 보도블럭의 개수가 1000개로 비교적 작은 개수이므로, N^2의 풀이법도 가능할 것으로 보입니다.

2.

i번째 타일에서 i+1~N번째 타일로 넘어가는 경우를 생각할 때, 1~i번째 타일은 해당 타일까지 이동할 때 필요한 에너지의 최소값을 저장해두고 있어야 합니다. 그래야지만, 다음 타일로 넘어갈 때에 필요한 에너지의 양을 계산할 수 있기 때문입니다.

-> dp를 이용한 풀이!

 

풀이

아이디어를 통해 얻은 것

아이디어 2를 통해 dp를 이용한 풀이를 하기로 결정했고, 아이디어 1을 통해 2중 for문을 사용해도 될 것으로 예상됩니다.

 

dp

우선, dp 배열을 sys.maxsize원소 N개를 넣어줍니다.(sys.maxsize는 python3에서 가장 큰 정수입니다.)

 

i번째 타일에서 다음 타일로 넘어갈 때 필요한 에너지를 저장하는 방식은 다음과 같습니다.

(물론 문제에서 제시한 규칙들을 지킬 경우에만 최소값을 구하게 했습니다.)

 

dp[i+k] = min(dp[i+k],dp[i]+(k-i)^2)

i번째 타일에서 i+k번째 타일로 이동가능할 경우, (현재까지 구한 i+k번째 타일로의 이동 에너지의 최소값)과 (i번째 타일에서 i+k번째 타일로의 이동할 때 필요한 에너지)를 비교해서 작은 값을 다시 dp[i+k]에 저장해줍니다.

 

위의 과정을 2중 for문을 통해 반복해줍니다.

 

dp[N-1]가 sys.maxsize라면 답은 -1이 되고,

dp[N-1]이 sys.maxsize가 아니라면 답은 dp[N-1]이 됩니다.

 

 

 

해결

dp를 이용하는 문제를 연속으로 풀게 되서 풀이방식을 비교적 빨리 떠올렷던 문제였고, N이 그렇게 크지 않다는 것을 봤던 것도 주요했던 것 같습니다.