[BOJ] 백준 19951. 태상이의 훈련소 생활

2024. 2. 27. 08:45· Java/BOJ

문제

https://www.acmicpc.net/problem/19951

 

19951번: 태상이의 훈련소 생활

2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연

www.acmicpc.net


풀이

 누적합을 이용해야하는 문제입니다.

 

1 ≤ N ≤ 100,000 

1 ≤ M ≤ 100,000 

1 ≤ a ≤ b ≤ N

 

 입력값의 범위가 위와 같아서, 누적합을 이용하지 않고 배열을 일일이 연산할 경우에는 시간 복잡도가 O(N^2)으로 1초의 시간 제한을 넘어가게 됩니다. 

 

  그래서 누적합 배열에 모든 숫자를 넣는 것이 아니라, 처음과 끝만 기록합니다.

       for(int i = 0;i<M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int k = sc.nextInt();
            sum[st] +=k;
            sum[ed+1] -=k;
        }

		 ...
         
        //누적합 배열 구하기
        for(int i =1;i<=N;i++){
            sum[i] += sum[i-1];
        }

 여기서 중요한 것은 ed+1에 역으로 k를 빼주는 것입니다. 이것은 누적합 배열을 구성할 때에 끝 부분 이후로는 초기화를 시켜주어야 하기 때문입니다.

 

 예를 들어 {-1, -1, -1 ,0, 0, 0} 의 누적합 배열을 만든다고 생각해보겠습니다. 여기서 st = 0, ed = 3, k = -1일 것입니다.

 

그럼 초기 sum[] 배열은 {-1,0,0,1,0,0} 이 됩니다.

 

 st부터 ed까지 sum[i] 를 sum[i-1]을 더해 구해야하는데, 끝나는 지점+1에 k의 반대 부호 값이 없다면 {-1,-1,-1,-1,-1,-1} 로 배열이 끝나지 않습니다. 즉 끝나는 시점 이후로는 다시 원상복구를 시키기 위해서 부호의 반대 값을 더해, 이후부터는 0으로 채워줄 수 있게 합니다.

 

이렇게 만든 누적합 sum[] 누적합 배열을 ground[] 배열에 더해주면 정답을 구할 수 있습니다.

 

 


정답

import java.util.Scanner;

public class B19951_태상이의훈련소생활 {

    static int N,M;
    static int[] ground;
    static int[] sum;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] ground = new int[N+1];
        int[] sum = new int[N+2];
        for(int i =1;i<N+1;i++){
            ground[i] = sc.nextInt();
        }
        for(int i = 0;i<M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int k = sc.nextInt();
            sum[st] +=k;
            sum[ed+1] -=k;
        }
        for(int i =1;i<=N;i++){
            sum[i] += sum[i-1];
            ground[i] +=sum[i];
        }
        for(int i =1;i<=N;i++){
            System.out.print(ground[i]+" ");
        }
    }
}

'Java > BOJ' 카테고리의 다른 글

[BOJ] 백준 14284. 간선 이어가기2  (2) 2024.03.19
[BOJ] 백준 1806. 부분 합  (0) 2024.03.19
[BOJ] 백준 25195. Yes or yes  (0) 2024.02.26
[BOJ] 백준 2573. 빙산  (0) 2024.02.22
[BOJ] 백준 11054. 가장 긴 바이토닉 부분 수열  (0) 2024.02.21
'Java/BOJ' 카테고리의 다른 글
  • [BOJ] 백준 14284. 간선 이어가기2
  • [BOJ] 백준 1806. 부분 합
  • [BOJ] 백준 25195. Yes or yes
  • [BOJ] 백준 2573. 빙산
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (178)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (33)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (6)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 이석복
  • 자바스크립트
  • 김영한
  • BOJ
  • 네트워크
  • 스택
  • 자바
  • 레디스
  • Java
  • 백준
  • JCF
  • 프로그래머스
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 한양대
  • 반효경
  • 큐
  • OS
  • 운영체제
  • 구현
  • 인프런

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[BOJ] 백준 19951. 태상이의 훈련소 생활
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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