[JS/C++][백준]19951_태상이의 훈련소 생활

문제 번호

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

 

 

 

알고리즘 분류

• 누적 합

 

문제 풀이

 처음 접해본 누적합 문제이다.

 누적합에 대한 개념은 알고있었는데 문제로 풀어본적이 없어서 다른분들의 설명을 참고하였다. 두개의 블로그는 동일한 설명을 하고있다. 아래 블로그 역시 위의 블로그의 설명을 참고하여 자신이 알아보기 쉽게 작성하셨다고 한다.

2022 KAKAO BLIND RECRUITMENT 1차 코딩테스트

 

19951번 태상이의 훈련소 생활

 설명이 단번에 이해되지는 않았다. (내가 못하기 때문에.......ㅜ)

 sum 배열은 문제에서 주어지는 연산을 한번에 수행하기 위해서 필요한 배열이다. 문제에서 조교들이 요구하는 과정을 모두 수행했을때 연병장의 각 칸이 얼마만큼 변해야 하는지 나타낸다. 예를들어 sum[4] = 4 라면 연병장의 4번째 칸은 +4 연산을 해주어야 한다.

 arry 배열은 연산기록을 위한 배열이다. 즉 arry 배열을 통하여 sum 배열을 생성하는 것이다.

처음에 [A,B] 구간이 주어질때 왜 arry[B+1] -= K 를 해야하는지 몰랐었다. 그런데 손으로 sum 배열을 직접 계산해보니 바로 알겠더라.(모를땐 해보는게 최고다.)

 

 아무튼 Node.js 로 풀이를 진행했는데 시간초과에 걸렸다. 로직이 잘못되어서 시간초과에 걸린줄 알았는데 아직까지 Node.js 통과자가 없는걸 확인하고 Node.js로는 풀기 어려운 문제라고 판단되어서 C++을 사용하여 동일한 로직으로 다시 풀었다. 그래서 두개의 코드를 모두 올린다.

 

전체코드 Node.js

const fs = require('fs').readFileSync('태상이의 훈련소 생활/input.txt').toString().trim().split('\n')
let NM = fs.shift().split(' ');
const N = Number(NM.shift());
const M = Number(NM.shift());

let ground = new Array(N + 1);
let temp = fs.shift().split(' ');
for (let i = 1; i <= N; i++) {
  ground[i] = Number(temp[i - 1]);
}

// 누적합을 계산하기 위한 과정.
let sum = new Array(N+1);
let arr = new Array(N+1).fill(0);
for (let i = 0; i < M; i++) {
  let A, B, K;
  temp = fs.shift().split(' ')
  A = Number(temp[0]);
  B = Number(temp[1]);
  K = Number(temp[2]);
  arr[A] += K;
  arr[B+1] -= K;
}

// 누적합을 계산한다.
for(let i=1; i<=N; i++){
  sum[i] = sum[i-1] + arr[i];
}

// 구한 누적합을 연병장에 적용시킨다.
let answer = '';
for(let i=1; i<=N; i++){
  ground[i] += sum[i];
  answer += ground[i] + ' ';
}

console.log(answer);

 

전체코드 C++

#include<iostream>
using namespace std;

void sol(int* ground, int N, int M, int* arr, int* sum) {
	int A, B, K;
	for (int i = 0; i < M; i++) {
		cin >> A >> B >> K;
		arr[A] += K;
		arr[B + 1] -= K;
	}
	for (int i = 1; i <= N; i++) {
		sum[i] = sum[i - 1] + arr[i];
	}
	for (int i = 1; i <= N; i++) {
		ground[i] += sum[i];
		cout << ground[i] << ' ';
	}
}

int main() {
	int N, M;
	cin >> N >> M;

	int* ground = new int[N + 1];
	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;
		ground[i] = num;
	}

	int* sum = new int[N + 2]{ 0, };
	int* arr = new int[N + 2]{ 0, };
	sol(ground, N, M, arr, sum);

	//system("pause");
	return 0;
}

특이사항