Programming Challenges 책을 보기 시작했다.
문제하나하나가 시간이 꽤 들거 같아서, 이론만 훓어보다가 백트래킹 부분 문제를 풀어볼까 했는데
재귀함수에 대한 경험을 좀더 키워야 겠다는 생각을 했다.
좀더 기본을 다지자는 차원에서 그냥 DIV2 easy나 돌련다;
SRM283 DIV2
class DiagonalDisproportion
{
public:
int getDisproportion(vector <string> m)
{
int n = m.size();
int a = 0, b = 0;
REP(i, n)
{
a += m[i][i]- '0';
b += m[i][n-1-i] - '0';
}
return a-b;
}
};
SRM284 DIV2
: 그냥 재귀로 구현하면 간단한 문제인데 어렵게 풀었다. 역시 재귀함수에 대해 연습이 필요함.
트럭에 들어가는 cratf를 vector로 리턴하라고 하면 이렇게 짜면 됨;;
class Truckloads
{
public:
vector<int> sub(vector<int> a, int l)
{
VI ret;
REP(i, a.size())
{
if( a[i] <= l ) ret.pb(a[i]);
else
{
ret.pb( a[i]/2);
ret.pb( ceil(a[i]/2.0) );
}
}
return ret;
}
int numTrucks(int n, int l)
{
VI a(1,n);
VI b;
while( *max_element(ALL(a)) > l )
{
b = sub(a, l);
a = b;
}
return b.size();
}
};
재귀를 이용해서 다시 짠 소스
class Truckloads
{
public:
int numTrucks(int n, int l)
{
if(n <= l) return 1;
return numTrucks(n/2, l) + numTrucks( (n+1)/2, l);
}
};
SRM285 DIV2
: 나중에 다시 한번 풀어보자.
class BasketsWithApples
{
public:
int removeExcess(vector <int> a)
{
sort(ALL(a));
int n = a.size();
int ret = 0;
REP(i, n)
ret = max(ret, (n-i)*a[i]);
return ret;
}
};
SRM286 DIV2
class CuttingPoles
{
public:
int countCuts(vector <int> p)
{
int av = 0;
int n = p.size();
REP(i, n) av += p[i];
av /= n;
int ret = 0;
while(1)
{
sort(ALL(p));
if( p[0] == p[n-1]) break;
int gab = p[n-1]-av;
p[0] += gab;
p[n-1] -= gab;
ret++;
}
return ret;
}
};
SRM287 DIV2
: 소팅이 알파벳 순인데.. 큰 순서로 소팅한 후, 동일하면 알파벳순서인줄 알고 삽질했다. 문제를 잘 보자..
set< pair<string,int>>대신 map<string, int>를 사용해도 됐다. 대부분 map을 썼네..
class CustomerStatistics
{
public:
string toStr(int num)
{
stringstream s;
s << num;
return s.str();
}
vector <string> reportDuplicates(vector <string> c)
{
sort(ALL(c));
set< pair<string, int> > m;
REP(i, c.size())
if(count(ALL(c), c[i]) > 1)
m.insert( make_pair(c[i], count(ALL(c), c[i])) );
vector< pair<string, int> > m1(ALL(m));
vector<string> ret;
REP(i, m1.size())
ret.pb( m1[i].first + " "+ toStr(m1[i].second) );
return ret;
}
};
SRM288 DIV2
class AccountBalance
{
public:
int processTransactions(int s, vector <string> t)
{
char c;
int a;
REP(i, t.size())
{
istringstream in(t[i]);
in >> c >> a;
if( c == 'C') s += a;
else s -= a;
}
return s;
}
};
SRM289 DIV2
: 괜찮은 문제.
class ObjectFall
{
public:
int howLong(int x, int y, vector <string> o)
{
vector< pair<int, pair<int, int> > > m;
REP(i, o.size())
{
int a, b, c;
istringstream in(o[i]);
in >> a >> b >> c;
m.pb( make_pair(a, make_pair(b, c)));
}
sort(ALL(m));
reverse(ALL(m));
int ret = y;
REP(i, m.size())
{
if( y < m[i].first) continue;
if( x >= m[i].second.first && x <= m[i].second.second)
{
x = m[i].second.second;
y = m[i].first;
ret += 5;
}
}
return ret;
}
};
SRM290 DIV2
: 평균은 int라는 구문이 문제에 있음에도 Red들은 val*size > sum 으로 평균보다 큰지를 비교한다;; 역시..
class SpeedTyper
{
public:
string lettersToPractice(string l, vector <int> t)
{
int n = t.size();
vector< pair<char, int> > m;
int avg = 0;
REP(i, n)
{
if( i== 0){
m.pb(make_pair(l[i], t[i]));
avg += t[i];
}
else{
m.pb(make_pair(l[i], t[i]-t[i-1]));
avg += t[i]-t[i-1];
}
}
avg /= n;
string ret;
REP(i, n)
if( m[i].second > avg ) ret += m[i].first;
return ret;
}
};
반응형