생각날때마다 올리는 블로그

http://icpc.me/4796 문제캠핑은 최대 P일 중에 L일 할 수 있다.주인공은 V일동안 쉬어라고 명 받았다.과연 캠핑을 최대 얼마나 할 수 있을것인가? 풀이일단 꽉 채우고 남는거를 보자꽉 채우는 일은 $\frac{V}{P}\times{L}$이다.남는 날은, V를 P로 나누었을 떄의 나머지이다.이 남는 날이 L보다 작으면, 남은 날은 다 캠핑하고, 아니면 L일동안 캠핑하고 쉰 다음에 가면 된다.따라서, $min(V\%P,L)$이다.최종식은 $\frac{V}{P}\times{L}+min(V\%P,L)$이다. 코드12345678910111213#include using namespace std;int main(){ int L,P,V,cnt=1; while(1) { scanf("%d %d %d",&L..

http://icpc.me/10818 문제배열이 있다 최대값과 최소값을 찾아라 풀이$O(N)$ : 순회하면서 찾기 / max_element,min_element 사용 $O(NlogN)$ : 정렬 후에 0번째와 n-1번째 부르기 이하 생략 코드12345678910#include using namespace std;int main(){ int n; scanf("%d",&n); vector v; for(int i=0,x;i

http://icpc.me/2143 문제배열 A와 B가 주어진다. 부분배열을 Ai,Ai+1,....,Aj로 정의내릴 때A와 B의 부분배열의 합이 T가 되는 경우의 수를 찾아라 풀이둘다 1000보다 작으므로 $O(N^2logN)$에 풀 수 있다.미리 A의 부분배열의 합을 map에 다 저장해놓은 다음에, B의 부분배열을 순회하면서 T에서 뺸 값이 존재하는지 확인한다.존재하면 더해주는 식으로 진행답의 범위가 int를 넘어갈 수 있다($\approx1000\times1000\times1000\times1000=10^{12}$)답을 long long로 해야한다는거에 조심하자 코드1234567891011121314151617181920212223242526#include typedef long long ll;usi..

http://icpc.me/10545 문제일반적인 2G 휴대폰의 키패드에서, 각각의 키패드가 다르게 작동한다.a를 누르면 b가, b를 누르면 c가... 이렇게 진행 될떄주어진 문자열을 만들기 위해선 어떤 키패드를 몇번 눌러야하는지 출력하라. 풀이단순 구현노가다이하 생략 코드123456789101112131415161718192021222324252627282930#include using namespace std;int cnt[27],press[27];int key[10];int main(){ cnt[0]=cnt[3]=cnt[6]=cnt[9]=cnt[12]=cnt[15]=cnt[19]=cnt[22]=1; cnt[1]=cnt[4]=cnt[7]=cnt[10]=cnt[13]=cnt[16]=cnt[20]=cnt..

http://icpc.me/10571 문제중량은 증가하면서 선명도는 감사하는 최대의 수열을 찾아라 풀이LIS 하듯이 하면된다. 코드123456789101112131415161718192021222324252627#include using namespace std;typedef pair pii;int main(){ int T; scanf("%d",&T); while(T--) { int x; scanf("%d",&x); vector v; double l1,l2; for(int i=0,l;i

http://icpc.me/1280 문제어떤 수가 주어지면, 그 전까지 주어진 수들까지의 절댓값 차들을 다 더한 값들을 다 곱해라. 풀이절댓값이 아니라 그냥 이면 계속 더한값들을 저장하면서 계산하는 식으로 진행하면 된다. O(N)하지만 절댓값이므로, 이렇게 구해주면 안되고, 주어진 수보다 큰값과 작은 값들의 합을 나누어서 진행해야한다.상인과 비슷한 테크닉으로 하면 된다.20만이 최대이므로 좌표압축할 필요도 없다세그먼트 트리로 관리하면 된다.앙 개꿀띠 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include using namespace std;const int N = 200005;const int..

http://icpc.me/2508 문제주어진 표에서>o

http://icpc.me/1895 문제주어진 표에서 3*3의 필터가 주어진다.이 필터내의 값들 중 T보다 큰 중앙값들의 개수를 구하라. 풀이R,C가 너무 작아서 걍 다 돌면서 벡터에 넣은 다음 정렬해서 5번째 값 비교하면 된다. 소스12345678910111213141516171819202122232425#include using namespace std;int main(){ int R,C,T; scanf("%d %d",&R,&C); int v[45][45]; for(int i=0;i