You Lead!!

목재개수 m이 충분할 경우를 고려하지 않아서 한번 틀렸다. Greedy 알고리즘을 적용하여, 가장 간격이 큰 것부터 나눠나가면 된다. int main() { ofstream fout ("barn1.out"); ifstream fin ("barn1.in"); int m, s, c; fin >> m >> s >> c; vector cow; REP(i, c) { int a; fin >> a; cow.pb(a); } sort(ALL(cow)); vector d; d.pb( make_pair(0, cow[0]) ); for(int i=1; i< cow.size(); i++) d.pb( make_pair(cow[i]-cow[i-1], cow[i]) ); sort(d.rbegin(), d.rend())..

Greedy 알고리즘의 가장 간단한 예이다. 가장 싼 우유부터 원하는 양까지 사들이면 된다. int main() { ofstream fout ("milk.out"); ifstream fin ("milk.in"); int n, m; fin >> n >> m; vector d; REP(i, m) { int a, b; fin >> a >> b; d.pb(make_pair(a, b)); } sort(ALL(d)); int cur = 0, ret = 0; REP(i, m) { if(n-cur > d[i].second ) { cur += d[i].second; ret += d[i].first*d[i].second; } else { ret += (n-cur)*d[i].first; break; } } f..

앞 문제와 거의 유사한 문제.. string fromDecimal(int n, int b) { string result; while(n>0) { if(n%b >= 10) result += 'A'+(n%b)%10; else result += '0' + (n%b); n/=b; } reverse(ALL(result)); return result; } bool is_pal(string s) { int n = s.size(); REP(i, n/2) { if( s[i] != s[n-1-i] ) return false; } return true; } int main() { ofstream fout ("dualpal.out"); ifstream fin ("dualpal.in"); int n, s; fin >> n >>..

진법변환에 대한 개념을 묻는 문제. string fromDecimal(int n, int b) { string result; while(n>0) { if(n%b >= 10) result += 'A'+(n%b)%10; else result += '0' + (n%b); n/=b; } reverse(ALL(result)); return result; } bool is_pal(string s) { int n = s.size(); REP(i, n/2) { if( s[i] != s[n-1-i] ) return false; } return true; } int main() { ofstream fout ("palsquare.out"); ifstream fin ("palsquare.in"); int n; fin >> n..

사전을 구축해 두고, 일치하는 string을 찾는 문제. int main() { ofstream fout ("namenum.out"); ifstream fin ("namenum.in"); ifstream fin_dict("dict.txt"); vector dict; string s; while(fin_dict >> s) dict.pb(s); fin >> s; char key[8][3] ={{'A','B','C'},{'D','E','F'}, {'G','H','I'}, {'J','K','L'}, {'M','N','O'}, {'P','R','S'},{'T','U','V'},{'W','X','Y'}}; int cnt = 0; REP(i, dict.size()) { string d = dict[i]; if( d...

어제 SRM이 있기전에 ACRush를 통해 알게된 USACO를 가봤다. 알고리즘 공부를 시작하는 사람들에게 추천한다고 해서 문제 몇개를 풀어봤는데, 문제들이 다들 괜찮은거 같다. 당분간 USACO의 문제들을 풀면서 연습을 해야겠음. 그런데, 여기는 단계에 문제를 못풀면 다음 단계로 넘어가질 못한다..ㄷㄷ; 오늘은 특별히 막히는 문제없이 6문제 풀이완료. TC에서 easy문제들을 좀 풀었던게 연습이 되서 그런지 쉬운 문제들은 금방 풀수 있는 자신감이 생기는거 같다. 그중에 마지막 문제였던 Transformations 풀이 소스를 기록. 90도, 180도, 270도를 각각 구현을 해놨는데, 90도 하나만 짜놓고, 여러번 호출하는 방법도 있었다. vector lotate(vector d, int num) { ..

오늘 새벽 0시에 있었던 매치였다. 250 easy문제는 평이한 문제였다. 500 mid문제가 중력개념이 나왔는데, 두 점만 주어질때는 구하겠는데, 3점이상 넘어갈 때를 어떻게 처리할지가 막막했다.. 이차방정식을 이리저리 변환해봐도 x를 구하기는 어려웠다. 나중에 푼 사람들 보니, 두 점을 반씩 나누면서, 점점 해로 좁혀나가는 방식으로 풀었더라.. 이런 비슷한 문제를 접해보지 못한 나로서는 참 막막했던 문제.. 1000 hard문제는 의외로 쉬워보였으나.. 시간이 얼마 안남아서, 못풀었다. 나중에 시간나면 찬찬히 한번 풀어봐야 겠다. Challenge Time에서는 500문제를 마감 1분전에 제출하는 사람이 있길래, 입력값을 좀 복잡하게 넣어봤다. 역시나 성공..ㅡㅡㅋ 그러나, 한번 성공한걸 탄력받아 다..

지난 금요일 저녁 8시에 있었던 매치.. easy와 mid문제는 난이도가 쉬웠던 편이었고, hard문제는 시간내에 풀기엔 아직 힘들었다. challenge time에 윤년 계산을 잘못한 사람이 있어, 하나 잡아내고, hard문제는 시간초과 나올 거 같아서 시도했더니 50%로 성공했다. 그럭저럭, 문제실수도 없어서 DIV에서 76위, 룸 4위로 다시 초록색이 됐다..ㅡㅡㅋ 이번 SRM이 있기 좀전에 SnapDragon 이라는 현재 TC 랭킹 4위인 사람이 채팅방을 만들어서, 알고리즘 공부를 시작하는 사람들에게 문답을 하고 있어서, 들어가서 좀 지켜봤는데 인상적이었던 답변들을 몇개 기록해 본다. 1. 알고리즘 공부를 시작하는 사람들에게 추천하는 방법은? -> 고등부 정보올림피아드 문제를 풀어보아라. 그다음에..

SRM396 DIV2 class VerifyCreditCard { public: string checkDigits(string c) { int odd = 1; if( c.size()%2 == 0) odd = 0; stringstream in; REP(i, c.size()) { int v = c[i] - '0'; if( odd == 1) { if( i%2 == 1) in

SRM386 DIV2 class TrophyShelf { public: vector countVisible(vector t) { VI ret; int m = 0, cnt = 0; REP(i, t.size()) { if( m = 0; i--) { if(m < t[i]) { m = t[i]; cnt++; } } ret.pb(cnt); return ret; } }; SRM387 DIV2 class GuessingNextElement { public: int guess(vector A) { int is_ari = 1; int dis = A[1] - A[0]; f..