[백준 13422번] 도둑

난이도: 골드 IV

문제 링크: https://www.acmicpc.net/problem/13422

13422번: 도둑

백준 13422번 문제 도둑

시간 제한 1초인 문제입니다.

문제의 요구점을 간단히 짚고 넘어가자면 다음과 같습니다.

• 배열 (집)은 원형으로 이루어져 있으며, 총 n개 (n은 10만 이하의 자연수)로 이루어져 있다.
• m은 도둑이 한번에 털어야 하는 집의 갯수이며, 총 n개 이하의 자연수로 이루어져 있다. 또한, 도둑은 서로 인접한 집만 털 수 있다.
• 각 경우의 수에 대해, 도둑이 턴 m개의 집의 금액의 총합이 k 미만이면 유효한 경우로 count한다.

하지만 모든 경우에 수에 대해 m번의 합연산을 한다면 어떻게 될까요?

집이 총 10만 개 있고, m = 5만이라고 생각해 봅시다.

총 5만개의 합연산을 10만 번 하게 됩니다. 즉 0.5n^2, 약 O(n^2)의 시간복잡도를 가지게 되며, 제한 시간 내에 완료할 수 없습니다.

 

제가 접근한 방법입니다.

맨 처음에 0번 원소부터 이어서 m개의 원소의 합을 구합니다. 이 합에 대해 k 미만인지 판별합니다.

그 다음부터 i = 0부터 시작해서 i < n-1을 만족하는 동안 i값을 1씩 증가시키며, i번째 원소를 앞에서 구한 합에서 빼고, i+m번째 원소를 앞에서 구한 합에 더합니다. 이 때, i+m이 n과 같거나 n보다 클 경우, n을 뺍니다.

이렇게 하면 이어진 m개의 원소에 대해, 원형 배열의 모든 경우의 수를 딱 1번씩만 확인하게 됩니다.

또한, 앞서 말한 것처럼 10만개의 원소 중 연속한 5만개의 합의 경우의 수를 구하는 경우, 맨 처음 5만번의 합 연산 이후로는 각 경우마다 2회의 합연산을 하게 됩니다. 따라서 O(n)의 시간복잡도를 가지게 됩니다.

 

코드는 아래와 같습니다.

앞으로는 테스트 케이스가 x회 주어지는 문제의 경우, 아래처럼 별도 함수로 분리하여 가독성을 높이고자 합니다.

 

조심해야 하는 경우는 n == m인 경우입니다.

n == m인 경우, loop을 돌아가며 각 경우를 확인할 필요 없이, 최초에 구한 합만을 판별하면 됩니다.

이를 위해 코드 내에 n == m인 경우를 판별하도록 해 두었습니다.

 

채점 결과

맨 처음에는 n == m인 경우를 생각하지 못해서 틀렸습니다 ㅠ

 

백준에서 골드 난이도 문제 중에 4~5는 상당히 쉽게 푸는 편인데, 1~2의 문제들은 한번씩 더 생각하게 되네요.

저도 더 공부하고 연습해서 골드 정도의 문제들은 쉽게쉽게 풀었으면 좋겠어요 ㅎㅎ