<Dovelet>6계단 - 로커스 록커

한창 정렬공부를 할 때 풀었던 알고리즘 문제다

문제는 내가 입력한 t분짜리 CD에 내가 입력한 곡들을 몇개 담을 수 있는지 출력하는 문제인데

딱봐도 정렬해서 시간이 가장 짧은 곡들 순서대로 담아서 출력하면 될 것 같다(지금보면 간단한데 그 때는 정말 힘들게 풀었던 것 같다)

http://59.23.150.58/30stair/rocker1/rocker1.php?pname=rocker1

당신은 유명한 그룹 로커스 록 그룹에 대한 아직 발표되지 않은 n(1<=n<=200) 곡의 노래에 대한 권리를 상속 받았다. 당신은 1 개의 cd 로 이 곡들을 발표할 계획이다. 각 cd 는 최대 t(1<= t <= 100) 분 노래를 저장할 수 있다. 당신은 이 노래의 예술적 가치를 판단할 수 없어 만들어진 순서대로 cd 에 가장 많은 노래를 수록하려고 한다.(물론 가장 많은 곡을 담는게 목표이기에 중간에 빠지는 노래도 발생할 수 있다) 입력형식 첫 줄은 두 개의 정수 n , t 이 입력된다. 다음 줄에 n 개의 노래들이 만들어진 순서대로 각 노래의 크기(100 보다 작은 자연수)가 입력된다. 출력 형식 출력은 1 개의 cd 에 담을 수 있는 최대 노래 수를 나타내는 정수하나를 출력한다.

#include <stdio.h> int a[1000]; int main(void) { int n,t,i,j,min_index,tmp,sum=0,k=0; scanf("%d %d",&n,&t); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n-1;i++) { min_index=i; for(j=i+1;j<=n-1;j++) { if(a[min_index]>a[j]) { min_index=j; } } tmp=a[min_index]; a[min_index]=a[i]; a[i]=tmp; } for(i=0;i<n;i++) { sum+=a[i]; if(sum>t) break; k++; } printf("%d",k); return 0; }

역시 항상 옛날에 풀었던 코드를 보면드는 생각이 변수이름이 조잡하다

이 문제를 무심히보다가 c++의 STL컨테이너를 사용하면 정렬없이 간단한코드로 풀 수 있을 것 같았다

몰론 로직이 더 간단하다고는 장담할순 없지만 한번 multiset을 이용해서 다시 한번 풀어보았다

#include<iostream> #include<set> using namespace std; int main(void) { multiset<int> m; int n, t; int input,dap=0; cin >> n >> t; for (int i = 0; i < n; i++) { cin >> input; m.insert(input); } for (multiset<int>::iterator iter = m.begin(); iter != m.end(); iter++) { if ((t-*iter) >= 0) { t -= *iter; dap++; } } cout << dap; return 0; }

확실히 STL컨테이너가 배우고나면 알고리즘 문제 푸는데는 굉장히 편한 것 같다