어흥
[백준 13422] 도둑 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/13422
1. 주의할 점
- N과 M이 같을때의 조건을 잘 세운다
- 최대 몇개를 확인하면 되는지 식을 잘 세운다
- While문 안에 For문을 이용하여 Sum을 계산하지 않는다 -> 두 포인터를 활용한다
2. 구현
- 입력받을 배열의 크기를 2배로 하여 N + M -1개의 배열에서 연속된 M개씩 고르도록 한다
- While문을 몇번 반복할것인지 Len을 구해야 한다. Len : 기존배열에서 한바퀴 더 돌아서 계산할 횟수
- 여기선 M = con으로 뒀으며, N = M이라면 추가로 0번, 같지 않다면 M-1번만 확인하면 된다
[설명]
N=4 그리고 1,2,3,4를 입력 받는다고 가정
Len식의 이유 1) M=2일 때
1 | 2 | 3 | 4 | 1(맨 앞의 1) |
O | O | |||
O | O | |||
O | O | |||
O | O |
=> 4번 확인
Len식의 이유 2) M=4일 때
1 | 2 | 3 | 4 |
O | O | O | O |
#include <iostream>
using namespace std;
long long money[200000];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int test, l, r, num, con, k, val, result, len;
long long sum;
cin >> test;
for (int t = 1; t <= test; t++) {
cin >> num >> con >> k;
//초기화
sum = 0;
result = l = 0;
r = con - 1;
len = (con == num) ? 0 : con - 1;
for (int i = 0; i < num; i++) {
cin >> val;
money[i] = val;
if (i < con) sum += val;
if (i < len) money[i + num] = val;
}
while (r < num + len) {
if (sum < k) result++;
r++;
sum += money[r];
sum -= money[l];
l++;
}
cout << result << '\n';
}
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 16947] 서울 지하철 2호선 (C++) (0) | 2020.09.15 |
---|---|
[백준 2143] 두 배열의 합 (C++) (0) | 2020.09.08 |
[백준 14391] 종이 조각 (C++) (0) | 2020.09.05 |
[백준 16971] 배열 B의 값 (C++) (0) | 2020.09.02 |
[백준 1904] 01타일 (C++) (0) | 2020.08.30 |
Comments