[백준/C++] 13422번. 도둑

연성·2021년 8월 9일

1. 문제

다음 그림과 같이 N개의 집이 순서대로 이웃하여 세워진 마을이 있다.

위 그림은 N = 8인 경우 마을의 모습이다. 위 그림과 같이 각각의 집은 순서대로 서로 이웃해 있으며, 첫 번째 집과 마지막 집 또한 이웃해 있다. 예를들면 3이 적힌 집은 9, 4가 적힌 집과 이웃해 있으며, 5가 적힌 집은 6, 7이 적힌 집과 이웃해 있다. 이 마을 사람들은 각자 자신의 집에 돈을 보관한다. 위 그림에서 각 집에 적혀 있는 숫자는 집마다 보관 중인 돈의 금액을 나타낸다. 어느 날 이 마을에 도둑이 들었다. 도둑은 이 마을에서 어떻게 도둑질을 할까 잠시 고민하다가, 빠르게 돈을 훔치고 달아나기 위해 M개의 연속된 집에서 돈을 훔치되, 돈을 훔칠 때는 각 집에 보관중인 돈을 전부 훔치기로 했다. 예를 들어 M = 3일 때, 위 그림에서 순서대로 3, 4, 7의 돈을 보관중인 집에서 총 14의 돈을 훔친 후에는 더 이상 돈을 훔치지 않고 달아나야 한다. 또 다른 예로는 순서대로 5, 6, 4의 돈을 보관중인 집에서 총 15의 돈을 훔친 후에는 달아나야 한다. 그러나 만약 도둑이 이 마을에서 총 K원 이상의 돈을 훔친다면 자동 방범장치가 작동하여 도둑은 바로 붙잡히게 된다. 예를 들어 M = 3, K = 15인 경우 위 그림에서 순서대로 3, 4, 7의 돈을 보관중인 집에서 도둑질을 한다면 총 도둑질한 돈이 14가 되어 붙잡히지 않고 달아날 수 있지만, 순서대로 5, 6, 4의 돈을 보관중인 집에서 돈을 훔친다면 총 도둑질한 돈은 15가 되고, 방범장치가 작동하여 도둑은 붙잡히게 된다.

마을을 이루고 있는 집의 개수 N, 도둑이 돈을 훔쳐야 할 연속된 집의 개수 M, 자동 방범장치가 작동하는 최소 돈의 양 K와 각 집에서 보관 중인 돈이 순서대로 주어질 때, 도둑이 붙잡히지 않고 무사히 마을을 빠져나가기 위해 돈을 훔칠 M개의 연속된 집을 고르는 방법의 수를 출력하는 프로그램을 작성하시오.
어우 길어...

2. 입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마을에 있는 집의 개수 N(1 ≤ N ≤ 100,000), 도둑이 돈을 훔칠 연속된 집의 개수 M(1 ≤ M ≤ N), 자동 방범 장치가 작동하는 최소 돈의 양 K(1 ≤ K ≤ 1,000,000,000, K는 정수)가 공백으로 구분되어 주어진다. 테스트 케이스의 둘째 줄에는 N개의 집에서 각각 보관중인 돈의 양이 시계방향 순서대로 공백으로 구분되어 주어진다. 돈의 양은 각 집이 이웃해 있는 순서대로 주어진다. 첫 번째 집과 마지막 집 또한 이웃하기 위해 입력의 첫 번째와 마지막이 서로 연결되어 있다고 가정하며, 각 집에서 보관 중인 돈의 양은 1이상 10,000이하의 정수이다.

3. 출력

출력은 표준 출력을 사용한다. 입력 받은 데이터에 대해, 도둑이 자동 방범장치에 붙잡히지 않도록 연속된 M개의 집에서 돈을 훔치는 방법의 가짓수를 한 줄에 1개씩 출력한다.

4. 풀이

투 포인터 문제
start와 end 두 개의 포인터를 조작해서 답을 찾는다.
start를 0으로 end를 m으로 초기화 한다.
start부터 end까지 돈의 합을 구한다.
- end를 m으로 했기 때문에 for-loop에서 조건문을 i < m으로 해야한다.
- 이렇게 하면 뒤에 값 변경하고 인덱스 변경할 때 좀 더 예쁘게 할 수 있다.
while-loop를 돌리며 현재 훔친 돈이 k원 미만이면 answer 값을 증가시킨다.
- while-loop 종료 조건을 start가 다시 0으로 돌아올 때로 잡았다.
- 처음 시작할 때 0인 것만 무시하면 되서 do-while-loop를 이용했다.
- 조건문에 중요한 조건이 n != m이다.
인덱스와 훔친 돈을 조절한다.

💡 n != m이 필요한 이유

예를 들어 길이가 3이고 3개의 연속된 집에서 훔친다고 가정하자.
(0, 1, 2), (1, 2, 0), (2, 0, 1) 세 가지 경우가 있다.
하지만 사실 다 같은 경우다.
이러한 경우가 생기지 않게 n과 m이 같으면 딱 한 번만 확인하게 해준다.
- 여기까지는 생각 안하고 do-while-loop를 썼는데 완벽한 해결방법이었다.

5. 처음 코드와 달라진 점

조건문에 n != m 조건식을 추가해주었다.

6. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100000];

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int testCase;
  cin >> testCase;
  
  for (int tc = 0; tc < testCase; tc++) {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
      cin >> arr[i];
    }

    int start = 0, end = m;
    int moneyStolen = 0;
    int answer = 0;
    for (int i = 0; i < m; i++) {
      moneyStolen += arr[i];
    }
    
    do {
      if (moneyStolen < k) {
        answer++;
      }
      moneyStolen -= arr[start];
      moneyStolen += arr[end];
      start = (start + 1) % n;
      end = (end + 1) % n;
    } while (start != 0 && n != m);
    
    cout << answer<<endl;
  } 
}

연성

이전 포스트

[백준/C++] 2230번. 수 고르기

다음 포스트

[백준/C++] 13422번. 도둑

코딩테스트