https://www.acmicpc.net/problem/21921
21921번: 블로그
첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다
www.acmicpc.net
c++로 백준 21921번 문제를 풀어보겠다.
문제
찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.
요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.
찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.
찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.
입력
첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.
둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.
출력
첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.
만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.
제한
- 1≤X≤N≤250,000
- 0≤ 방문자 수 ≤8,000
예제 입력 1 복사
5 2
1 4 2 5 1
예제 출력 1 복사
7
1
<문제 풀이>
처음에 작성한 코드는 다음과 같다.
위에서 작성한 코드는 visual studio에서는 잘 돌아갔지만 백준 사이트에서는 '시간 초과'라고 떴다.
다시 작성해 최종적으로 제출한 코드는 다음과 같다.
'시간 초과' 문제를 해결하기 위해 N개의 수를 한번에 입력받아 sum을 계산하는 방법이 아닌, 0부터 X-1번째까지 X개의 수를 먼저 입력받아 sum에 저장하고 나머지를 입력받는 식으로 작성해야 했다.
1. N, X 값을 선언한 후 입력받는다.
2. N개의 숫자를 넣을 배열 arr을 선언한다.
3. 먼저 0부터 X-1번째까지 X개의 숫자를 입력받아 배열에 저장하고 sum 값을 계산한다.
4. 이후에 X번째부터 N-1번째까지 숫자들을 순차적으로 입력받으며, 하나의 수를 입력받을 때마다 sum을 다시 계산해 max와 days값을 다시 선언해준다.
(sum값에 새로 입력받은 arr[i]값을 더하는 대신 가장 앞의 값인 arr[i-X]값은 뺀다.)
(이렇게 새로 계산한 sum 값이 max 값과 같다면 days를 하나 올려주고, sum이 max보다 크다면 max값을 다시 선언 하고 days값도 1로 다시 초기화한다.)
5. max 값이 0이라면 "SAD"를 출력하고, 아니라면 max와 days 값을 출력한다.
'C++' 카테고리의 다른 글
| [백준 알고리즘] 4344번 : 평균은 넘겠지, c++ (0) | 2022.02.22 |
|---|---|
| [백준 알고리즘] 5032번 : 탄산 음료, c++ (0) | 2022.02.22 |
| [백준 알고리즘] 2490번 : 윷놀이, c++ (0) | 2022.02.21 |
| [백준 알고리즘] 10866번 : 덱, c++ (0) | 2022.02.21 |
| [백준 알고리즘] 2740번 : 행렬 곱셈, c++ (0) | 2022.02.20 |