728x90
문제
https://www.acmicpc.net/problem/2437
사용한 알고리즘
- 2022.01.11 - [PS/Algorithm] - [알고리즘 개념정리] 1. 정렬 (sort STL), 특정 변수 기준으로 정렬하기
- 2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디
풀이
- 각 추의 무게를 오름차순 정렬한다.
- 다음 추의 무게가 이전 추까지의 누적(무게)합+1 보다 크면
측정할 수 없는 무게의 최솟값은 누적합+1 이 된다.
예시)
추의 무게 : 1 1 2 3 6 7 30
누적 합 : 1 2 4 7 13 20 50
이때 무게가 7인 추가
누적합+1보다 큰 수인 15였다면
14를만들지 못하므로 답은 누적합+1인 14이다.
소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// 다음숫자가 누적합+1보다 크면 누적합+1 표현불가
int n; cin>>n;
int a[1001];
for(int i=0; i<n; i++) cin>>a[i];
// 1. 각 추의 무게를 오름차순 정렬한다.
sort(a,a+n);
/*
2. 다음 추의 무게가 이전 추까지의 누적(무게)합+1 보다 크면
측정할 수 없는 무게의 최솟값은 누적합+1 이 된다.
*/
int sum=0;
for(int i=0; i<n; i++){
if(a[i]>sum+1){
cout<<sum+1;
return 0;
}
else sum+=a[i];
}
cout<<sum+1;
return 0;
}
728x90
'PS > Baekjoon' 카테고리의 다른 글
[백준/C++] 2866번: 문자열 잘라내기(G5) (0) | 2022.01.17 |
---|---|
[백준/C++] 5525번: IOIOI(S2) (2) | 2022.01.16 |
[백준/C++] 9009번: 피보나치(S1) (0) | 2022.01.14 |
[백준/C++] 1431번: 시리얼번호(S3) (0) | 2022.01.12 |
[백준/C++] 18870번: 좌표 압축(S2) (0) | 2022.01.11 |
댓글