1. Number thinking 문제요약: Up and Down 을 Interactive 로 옮겨 놓은 문제이다. 풀이: 숫자 범위를 L 이라고 할때, 항상 현재 범위의 중간을 확인하는 방식으로 [log2 (L)] + 1 번 만에 정답을 맞출 수 있다. Interactive probolem 이기 때문에, 출력 시 buffer flush 를 해주지 않으면 TLE 로 판정된다. 2. Mural 문제요약: 길이 N 개의 벽이 있고, 각 벽에 해당되는 점수가 있다. 하루 마다 길이 1 에 해당되는 벽을 색칠 할 수 있고, 하루마다 좌우측 벽 중 색칠되지 않은 놈들중 하나가 무너진다. 첫번째 날에는 아무 벽에서 색칠을 시작 할 수 있고, 시작한 이후에는 이미 색칠된 벽의 좌우만 칠 할 수 있다. 이러한 상황에서..
KOI 2011 지역본선 책장
Problem https://www.acmicpc.net/problem/2466 Summary N 개의 책이 주어진다.각 책 마다 너비 W 와 높이 H 가 주어지고, 주어진 순서대로 책장에 꽂으려 한다. 모든 책을 꽂기 위한 책장의 너비와 높이중 최대값을 최소로 하려고 할 때, 그 최소값은 얼마일까? Solution 너비와 높이 중 최대값을 최소로 하는 문제이다.모든 책을 꽂아야 하는 책장의 특성상 너비가 증가함에 따라 높이가 단조감소하고, 너비가 줄어들면 높이가 단조증가하게 된다.따라서 책장의 너비(폭) 을 고정시키고, 그 때의 최소 높이를 구한 다음 그 높이를 기준으로 책장의 너비를 늘릴지 줄일지 결정할 수 있고 따라서 이 문제는 파라메트릭 서치로 접근 가능하다. 그렇다면 책장의 너비를 고정 시켰을 ..
오일러 파이 함수란 = 1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수이다로 정의되는 함수이다. 이러한 파이 함수에는 여러가지 성질이 발견되는데우선 곱의 함수라는 점이다.이에 대한 증명은 에라토스테네스의 채와 비슷하게 정수들을 쭉 나열한 다음, 서로소가 아닌 수들을 지워나가면 규칙을 찾을 수 있다. 이러한 파이 함수의 값을 구하는 방법에는 여려가지가 있겠지만,우선 특정 N에 대해 구한다고 생각하면N의 소인수들을 다 구한 다음 이 공식을 사용하면 된다. 1~ 까지 파이 함수의 값을 구하기 위해서는,소수판별을 할때 에라토스테네스의 채 기법을 사용한다. pi[i] = i;for (int i=2;i