알고리즘/acmicpc
-
2109알고리즘/acmicpc 2015. 2. 22. 16:09
처음에 문제 이해못해가지고 왜 이런걸 틀리지 싶었는데 내가 틀렸다 ㅡㅡQnA에서 문제를 제대로 이해하고 다시 풀어서 맞았다. 이 문제의 핵심은 d 기간 내에는 어떤 날짜에 강연을 해도 상관 없다는거다 그래서 3 1 1 10 2 10 2 라는 인풋이 들어오면정답으로 20을 출력해야한다. 어떤 강연을 할 지 말지 결정하는 과정은 다음과 같다. 기간내에 강연 할 수 있는 빈 시간이 있다면강연을 하고 이미 강연이 다 차있다면 차있는 강연들 중에서 가장 돈을 조금 주는 강연과 비교 한 다음하려고 하는 강연이 더 돈을 많이 주면 가장 돈을 조금 주는 강연과 바꾸면 된다. 생각 과정은 그리 어렵지 않은데 자료 구조를 어떤걸 쓸 것인지가 고민이었다.최대 10000개의 강연이 있기 때문에 생각하기 쉬운 자료구조(n*n)..
-
9463알고리즘/acmicpc 2015. 2. 21. 23:39
자력으로 해결하지 못했다. 다른사람이 푼 해설지 보고 어찌어찌 풀었는데음... 시간 문제는 BIT를 이용해서 해결하는 거로 하고 여기서 명심해야할 거는간선의 개수를 구하는 방법인데... 놀라웠다. 지금까지 나는 기를 쓰고 어케 풀어볼려고 생각했는데간단히 현재까지의 간선의 개수 - 연결된 간선의 위치 까지의 간선수로 한번에 해결 음 그니까 read(N) - read(v[i].second)라는 코드로 한번에 해결했다. 왜 나는 이런게 떠오르지 않을까 지금 생각해보면 정말 간단한 원리인데 원래 N*N에 얽매여서 자력으로 해결하지 못하고ㅠ 또 신기한거는 시간차인데 출력형식이 시간에 영향을 많이 준다.그런데 int보다는 long long이 출력할 때 빠르다. printf("%d") 로 출력하면 시간초과가 뜨는데p..
-
2776알고리즘/acmicpc 2015. 2. 21. 21:45
암기왕 문제..예상외로 쉽게 풀릴수 있는 문제인데 괜히 어렵게 풀었다.속도도 내 알고리즘이 더 빠를 줄 알았는데 오히려 더 느렸고 메모리도 더 많이 잡아먹고..모두 한꺼번에 모아서 sort함수 때리고 앞의꺼랑 뒤에꺼가 같으면 ok라 놓고 풀었는데계속 오답이 나왔다.. 오답의 원인을 찾으니까 내 알고리즘은 검사를 두 번 실시하면 안에있는 거로 간주하는 문제가 있었다.. 아 진짜 이런 찐따가 따로없다.. binary_search라는 stl이 있어서 빠르게 해결 할 수 있었다... 이런거는 빨리 알아야 하는데아 그리고 왠만하면 cin, cout을 쓰지 말고 #include에서 printf, scanf를 사용하는 습관을 들여야 겠다. cin, cout이 5배나 더 느리다니... 이것도 cin, cout 썼으면 ..
-