[알고리즘/문제] 백준 2979번: 트럭 주차 (C++)

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

2979번: 트럭 주차

#include <iostream>

using namespace std;

int A, B, C, a, b, c[100], sum=0;

int main() {
	cin >> A >> B >> C;
	for (int i = 0; i < 3; i++) {
		cin >> a >> b;
		for (int j = a; j < b; j++) c[j]++;
	}
	for (int k = 0; k < 100; k++) {
		if (c[k]) {
			if (c[k] == 1) sum += A;
			else if (c[k] == 2) sum += 2 * B;
			else if (c[k] == 3) sum += 3 * C;
		}
	}
    
	cout << sum << '\n';
	return 0;
}

 

이번 문제는 어떻게 풀어야하는지 생각을 좀 많이했다.

처음에는 누적합일 것이라 생각했다.

왜냐하면 트럭이 각각 주차된 시간을 누적해서 더하면 되지 않을까 생각했다.

하지만 너무 복잡해졌고 결국 풀이를 봤다.

 

이 문제는 카운팅 문제였다.

전혀 예상하지 못했다.

 

이런 문제처럼 특정 구간이 저장되어야 하고 중복될수도 있는 식의 문제는 카운팅 배열로 해결하는 것 같다.

이런 문제 유형을 '구간 칠하기'라고도 하는 것 같다.

 

카운팅 배열로 풀어야한다는 것을 보고 다시 코드를 작성했다.

문제를 어떻게 풀어야할지를 아니 코드를 짜는 것은 그렇게 어렵지 않았다.

 

주의할 점은 이런 도착, 출발 시간등이 있는경우

도착한 시간은 포함, 떠난 시간은 미포함이다.

무슨 뜻이냐면

for (int i = 도착시간; i< 떠난시간 ; i++)

위 for문과 같이 종료조건에 등호를 붙이지 않아야 한다는 것이다.

 

 

[인프런 강의]

https://inf.run/QKBXL

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 - 인프런