[백준 1758] 알바생 강호 - C++

BOJ Link

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

 

풀이 과정

순서에따라 받을돈에 0..-1..-2..-(N-1) 원이 차감된다. 이 때 합(받을돈-차감된 돈)이 음수일 경우, 0으로 치기 때문에 그리디하게 풀 수 있다. 그렇지 않다면 순서에 상관없이 똑같은 돈을 받을 것이다.

 

따라서, 내림차순으로 정렬하여 합을 누적하고 출력한다.

 

제출 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int N;
	std::cin >> N;

	std::vector<int> vec(N);
	
	for (int i = 0; i < N; i++) {
		std::cin >> vec[i];
	}

	sort(vec.begin(), vec.end(), std::greater<>());
		
	long ans = 0;
	long minus = 0;
	for (int e : vec) ans += std::max(0L, static_cast<long>(e) - minus++);

	std::cout << ans;

	return 0;
}

 

배운 점

1. sort시 predicate인 greater<>()가 있다.

<>안에 인자가 없으므로 자료형을 자동으로 추론할 것이다. 즉, int가 대입될 것이다.

(추론 기능은 c11부터 추가됐다고  한다.)

 

2. (long) e와 static_cast<long>(e)의 차이이다.

static_cast는 컴파일 단계에서 타입 오류를 체크한다.

또한, 가독성이 좋으므로 형변환 의도를 명시할 수 있다. 고로 권장된다.

 

3. vec.at(i)과 vec[i]의 차이이다.

컨테이너의 vec.size() = 5일 때, 10번째 원소에 접근한다고 가정하면,

 

at(10)은 std::out_of_range를 던진다. 고로 에러이다.

vec[10]은 undefined behavior이다. 실행환경에 따라 예상치 못한 동작이 발생한다.

(또한, ub는 "예상치 못한 동작"이 아닌 "C++ 표준에서 정의하지 않은 동작" 을 칭한다.)

 

내 환경에서 vec[10]을 접근했을 땐, segmentation fault error를 OS에서 띄워줬다.

(IDE/컴파일러가 띄워주는 것이 아님)

 

그렇다면 무조건 at()을 쓰는게 좋냐 하면 그건 또 아니다.

[]를 통한 인덱스 접근은 성능에 이점이 있다. 오류체크 등에 소모하는 오버헤드가 없다.

큰 차이는 아니겠지만 이를 trade-off할 수 있다.