백준 11399번 : ATM

링크 : https://www.acmicpc.net/problem/11399

문제읽기

정렬. 그리티 탐색 문제.

작은 순서대로 배열해야 최솟값이 나올 것 같다. 시작해보자. 그럼 이걸 어떻게해야 작은 순서대로 정렬할 수 있을까? 자료구조 문제이다.

코드

Ver 1.

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

int arr[1001], sum[1001], result[1001];
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr,arr+N);
	result[0] = sum[0] = arr[0];
	for (int i = 1; i < N; i++) {
		sum[i] = arr[i] + sum[i - 1];
		result[i] = result[i - 1] + sum[i];
	}
	cout <<result[N-1];
	return 0;
}

Ver 2.

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

int arr[1001], sum[1001];
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr,arr+N);

	sum[0] = arr[0];
	int tmp = sum[0];
	for (int i = 1; i < N; i++) {
		tmp = sum[i] = arr[i] + tmp;
		sum[i] = sum[i - 1] + sum[i];
	}
	cout <<sum[N-1];
	return 0;
}

분석

sort하는 것은 알고리즘 라이브러리의 힘을 빌렸다.

result[0] = sum[0] = arr[0];
for (int i = 1; i < N; i++) {
	sum[i] = arr[i] + sum[i - 1];
	result[i] = result[i - 1] + sum[i];
}

이 부분은 피보나치 수열처럼 접근할 수 있었다. 하지만 result 배열을 사용하지 않고 사용할 수 있지 않을까? 고민해보자.

해서

sum[0] = arr[0];
int tmp = sum[0];
for (int i = 1; i < N; i++) {
	tmp = sum[i] = arr[i] + tmp;
	sum[i] = sum[i - 1] + sum[i];
}

tmp 변수를 사용했다. 당연한 소리지만 int 변수 하나 선언해서 사용하는 것이 배열 1001개 선언하는 것보다 더 효율적이다.