This is my Life ::

SRM 145 DIV2 250 - ImageDithering

TopCoder 2011/01/15 00:40

Class:	ImageDithering
Method:	count
Parameters:	string, vector <string>
Returns:	int
Method signature:	int count(string dithered, vector <string> screen)
(be sure your method is public)

dithered에 있는 알파벳이 screen에 얼마나 많이 있는지 알아네는 문제이다.

처음 생각한 방법은 알파벳이 26개 이니까, 배열로 int를 26개 잡아서 각 문자가 얼마나 들어가 있는지 계산하려고 했었지만 이렇게 하면 곱셈이 들어가고 메모리도 많이 잡아야 하며

심지어 문자를 찾는데 switch-case를 사용하려고 했었으니까 코드 라인도 만만치 않게 나왔을 것 같다.

그래서 메모리를 적게 먹으면서 빠르게 계산할 수 있는 방법을 생각해 봤다.

바로 bit 단위로 비교하는 방법이다. 알파벳이 26개(32개 이하)이므로 변수 하나만 선언하면 해당 문자가 있는지 없는지 확인할 수 있다.

'TopCoder' 카테고리의 다른 글

SRM 145 DIV2 250 - ImageDithering (2)	2011/01/15
SRM 415 DIV2 250 CollectingUsualPostmarks (0)	2008/09/03
SRM 413 DIV2 250 Subway2 (0)	2008/08/20

Posted by yongseok

TAG ImageDithering, SRM145, TopCoder

트랙백이 없고, 댓글 2개가 달렸습니다

SRM 415 DIV2 250 CollectingUsualPostmarks

TopCoder 2008/09/03 20:55

이번 문제는 내가 지금까지 풀어본 TopCoder 문제 중에서 가장 쉽게 풀었던 문제였던것 같다

parameter가 두가지 주어진다
prices와 have
prices는 각 우표의 가격을 나타내고
have는 이 중에서 자신이 가지고 있는 우표를 나타낸다

return value는 현재 자신이 가지고 있는 우표를 돈으로 바꿔서 최대한 많은 종류의 우표를 샀을때
몇개의 우표를 가질 수 있는지를 넘겨주면 된다.

#include <vector>
#include <algorithm>

typedef unsigned int uint;

using namespace std;

class CollectingUsualPostmarks {
public:
int numberOfPostmarks(vector <int> prices, vector <int> have) {
   int rr = 0;
   int cash = 0;
   uint i;

   // Exchange
   for(i=0 ; i<have.size() ; i++) {
cash += prices[ have[i] ];
   }

// Purchase
sort(prices.begin(), prices.end());

   for(i=0 ; i<prices.size() ; i++) {
cash -= prices[i++];

if(cash<=0) {
   return rr;
}
rr++;
   }

return rr;
}
};

'TopCoder' 카테고리의 다른 글

SRM 145 DIV2 250 - ImageDithering (2)	2011/01/15
SRM 415 DIV2 250 CollectingUsualPostmarks (0)	2008/09/03
SRM 413 DIV2 250 Subway2 (0)	2008/08/20

Posted by yongseok

TAG 415, CollectingUsualPostmarks, SRM, srm415, TopCoder

트랙백이 없고, 댓글이 없습니다.

SRM 413 DIV2 250 Subway2

TopCoder 2008/08/20 02:29

간단한 물리계산으로 풀 수 있는 문제이다

거리와 최대 가속도 그리고 최대 속도가 정해진 상태에서

최단 시간을 묻는 문제인데

다음의 두 가지 경우로 나눠서 생각할 수 있다.

1. 자동차가 최대속도까지 가기전에 다시 속도를 줄이는 경우

2. 자동차가 최대속도에 도착한 다음에 일정 거리를 달린 다음에 속도를 줄이는경우

#include <iostream>
#include <cmath>

using namespace std;

class Subway2 {
public :
double minTime(int length, int maxAcceleration, int maxVelocity)
{
double len, a, vmax, t_len;
len = (double)length; // casting을 위하여 저장
a = (double)maxAcceleration;
vmax = (double)maxVelocity;
t_len = (vmax*vmax)/a; // vmax까지 속도를 올렸다가 내려왔을때의 거리

if(len < t_len) {
return 2.0*sqrt(len/a);
}
else {
return (len - t_len)/vmax + (vmax/a)*2;
}
}
};