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

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

www.acmicpc.net/problem/19951

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

 

 

 문제

 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.

 연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 b번 칸까지 높이 k만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.

 태상이는 각 조교의 지시를 각각 수행하면, 다른 조교의 지시로 흙을 덮어둔 칸을 다시 파내기도 하는 비효율적인 일이 발생하는 것을 깨달았다. 그래서 태상이는 각 조교의 지시를 모아 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하려고 한다.

 불쌍한 태상이를 위해 조교들의 지시를 모두 수행한 뒤 연병장 각 칸의 높이를 구하자.

 

 입력

첫 줄에 연병장의 크기 N과 조교의 수 M이 주어진다.

둘째 줄에 연병장 각 칸의 높이 Hi가 순서대로 N개 주어진다.

셋째 줄부터 M개의 줄에 각 조교의 지시가 주어진다.

각 조교의 지시는 세 개의 정수 a, b, k로 이루어져 있다.

• k ≥ 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 늘어나도록 흙을 덮어야 한다.
• k < 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 줄어들도록 흙을 파내야 한다.

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• -10,000 ≤ Hi ≤ 10,000
• N, M, Hi는 정수
• 조교의 지시
  • 1 ≤ a ≤ b ≤ N
  • |k| ≤ 100

 

 출력

모든 지시를 수행한 뒤 연병장 각 칸의 높이를 공백을 사이에 두고 출력한다.

 

 

 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N, M; cin >> N >> M;
	vector<int> v, temp;
	v.push_back(0);
	temp.push_back(0);
	for(int i=0;i<N;i++){
		int a; cin >> a;
		v.push_back(a);
		temp.push_back(0);
	}
	
	for(int i=0;i<M;i++){
		int a, b, c; cin >> a >> b >> c;
		temp[b] += c;
		temp[a-1] -= c;
	}
	
	for(int i=N;i>=1;i--){
		temp[i-1] += temp[i];
	}
	
	for(int i=1;i<=N;i++){
		v[i] += temp[i];
		cout << v[i] << ' ';
	}
	
	return 0;
}

 최근에 코딩테스트 준비하는 하느라 문제는 많이 풀었는데 포스팅하지 못했다. 몰아서 올려보고자 한다.

먼저 얼마전 카카오 코딩테스트 6번문제에서 효율성 처리와 관련된 문제이다. 누적합을 이용하여 시간복잡도를 크게 줄일 수 있는 문제이다. temp의 각 인덱스의 값이 의미하는 바는 1번부터 해당 인덱스까지 더해줘야할 값이다. 예를 들어, 2번부터 5번까지 2만큼 더해줘야 한다면 temp[5]에 2를 더하고 temp[1]에 -2를 해줌으로써 해결할 수 있다. A~B까지 일일히 더하면 O(N^2)으로 시간초과가 당연하다. 무튼 위 방법으로 temp를 완성하고 나면 기존 v에 더해줘야 한다.

더하는 과정에서도 이중포문으로 값을 더해주면 O(N^2)으로 시간초과가 나게 되는데, temp를 뒤에서부터 바로 앞의 것을 더해주는 방식으로 O(N)만에 해결할 수 있다. 새롭게 만든 temp를 v에 더해주기만 하면 최종적으로 O(2*N)으로 문제가 풀린다. 즉, O(M + 2*N)의 시간복잡도로 풀리는 문제이다.

이런 과정을 2차원 배열에서 처리하는 것이 카카오 문제였다. 2차원 배열에서도 비슷한 방식으로 풀릴 것 같다.