[BOJ] 11399번 : ATM

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
int p[1005]; 
int d[1005];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	for (int i = 1; i <= n; i++) cin >> p[i]; 
	sort(p + 1, p + n + 1); 
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		d[i] = d[i - 1] + p[i];
		ans += d[i];
	}
	cout << ans << '\n';
	
}

누적합이 계속 더해지는 문제이다 보니, 최솟값부터 처리하는 게 맞다는 생각이 들었다. 따라서, greedy 전략이 필요하다.  

이 과정에서 정답인 32가 안 나오고, 13이 나왔다. 디버깅을 해보니, 누적합을 더해야 하는데, 그냥 부분합만 출력해서 답이 제대로 나오지 않았다. 따라서, ans = 0을 설정해 주고, 각 테이블의 값을 더해주었다. 테이블을  설정하다 보니, dp와 비슷하게 보였다. 

 

3. solution 2 :

// Authored by : heheHwang
// Co-authored by : -
// http://boj.kr/2422d605017041259db67ccc36416aad
#include <bits/stdc++.h>
using namespace std;

int N, ans;
int P[1002];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  for (int i = 0; i < N; i++) cin >> P[i];
  sort(P, P + N);
  for (int i = 0; i < N; i++) ans += P[i] * (N - i);
  cout << ans;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/11399.cpp

basic-algo-lecture/0x11/solutions/11399.cpp at master · encrypted-def/basic-algo-lecture

이 풀이에서 신기한 점은 ans += p [i] * (N - i)이다. (나는 풀이를 one-index로 했기 때문에 약간은 달라진다.) 

테이블에 저장하지 않고, 최종값에는 N- i번만큼 더해지니, 이것을 이용했다.