[BOJ] 블로그 21921번 C++

2024. 3. 31. 17:40· Algorithm

 

 

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

 

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

 

입력

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

 

접근 방식

 

단순히 반복문을 사용하면 시간초과가 발생한다

그래서 누적합을 사용해서 풀이를 해주었다

어쩌피 X일동안 들어온 방문자를 구하기 때문에

투포인터를 사용해

시작 ~ 시작 + X일 -1 (X일 포함이기 때문에 -1 해줌)의 누적합을 구해서

만약 최댓값보다 크면 최댓값을 갱신하면서 기간을 저장해주는 ans 변수를 1로 초기화해준다

최댓값과 같다면 ans ++;해준다

모든 조건문을 검색했다면 시작일을 변경해준다!

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N,X, ans = 0, mx = 0;
int pSum[250002];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N>>X;
    for(int i=1; i<=N; i++) {
        int x; cin>>x;
        pSum[i] += pSum[i-1] + x;
    }

    int st = 1;
    int en = X;


    while(en <= N) {
        int tmp = pSum[en] - pSum[st-1];
        if(mx < tmp) {
            mx = tmp;
            ans = 1;
        }
        else if(mx == tmp) ans++;
        st++;
        en = st + X-1;
    }

    if(mx == 0) cout<<"SAD";
    else {
        cout<<mx<<'\n'<<ans;

    }
}

 

+ 추가( 단순 반복문으로도 풀 수 있다 )

#include<bits/stdc++.h>
using namespace std;

int N, X, mx = 0, cnt = 1;
int pSum[250005];

int main() {
    cin >> N >> X;
    for(int i = 1; i <= N; i++) {
        int m;
        cin >> m;
        pSum[i] = pSum[i-1] + m;
    }

    for(int i = 0; i <= N - X; i++) { 
        int tmp = pSum[i + X] - pSum[i]; 
        if(mx == tmp) cnt++;
        else if(mx < tmp) {
            cnt = 1;
            mx = tmp;
        }
    }

    if(mx == 0) cout << "SAD";
    else {
        cout << mx << '\n' << cnt;
    }

    return 0;
}

 

'Algorithm' 카테고리의 다른 글

[BOJ] 가장 긴 짝수 연속한 부분 수열 (large) 22862번 C++  (1) 2024.04.03
[BOJ] 겹치는 건 싫어 20922번 C++  (0) 2024.04.02
[BOJ] 나머지 합 10986번 C++  (0) 2024.03.28
[BOJ] 수들의 합 4 2015번 C++  (0) 2024.03.26
[BOJ] 귀찮아 (SIB) 14929번 C++  (0) 2024.03.25
'Algorithm' 카테고리의 다른 글
  • [BOJ] 가장 긴 짝수 연속한 부분 수열 (large) 22862번 C++
  • [BOJ] 겹치는 건 싫어 20922번 C++
  • [BOJ] 나머지 합 10986번 C++
  • [BOJ] 수들의 합 4 2015번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 데이터베이스
  • BOJ
  • 스택
  • Stack
  • 문자열
  • dp
  • 모던 자바스크립트 딥다이브
  • javascript
  • 누적합
  • 모던 리액트 딥다이브
  • 탐욕 알고리즘
  • 우선순위 큐
  • typescript
  • CS
  • 자바스크립트
  • Fe
  • react
  • 그리디
  • 리액트
  • 투 포인터
  • 백준
  • BFS
  • Greedy
  • C++
  • 백트래킹
  • 완전탐색
  • 그래프 탐색
  • 알고리즘
  • 자료구조
  • TOPCIT

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 블로그 21921번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.