Codeforces Round #319 div2
A n by n 행렬이 주어진다. a(i,j)에는 i*j가 써져있다. 1<=i,j<=n이다. 이 행렬에 쓰인 숫자 중 x와 같은 것들의 갯수를 구하는 문제이다. 행렬의 각 열과 각 행을 봤을때 같은 숫자는 없다. 따라서 1~n까지 돌리면서 x의 약수이면서 x를 나눴을때 n이하의 숫자가 나오는 것들만 갯수를 세면 된다. O(n) B 1<=n<=10^6 , 1<=m<=10^3 길이 n 의 수열이 주어진다. 이 중 1개 이상의 숫자를 뽑아서 합해서 m의 배수를 만들 수 있는지를 구하는 문제이다. m의 배수라는 것은 결국 합했을때 m으로 나눈 나머지가 0이라는 것을 의미한다. 따라서 주어진 수열에서 중요한것은 그 숫자가 아니라 나눈 나머지이다. DP(i,j)를 현재 i 번째 나머지숫자를 보고 있을때 현재까지 합한 숫자들의 나머지가 j인 경우가 있는가? 라고 정의하면 dp[i][j]가 1일 때 dp[i+1][j+a[i]]를 1이라고 하면 된다. 이 경우O(n*m)으로 풀 수 있다. 문제는 n이 최대 100만이라는 것인데(TLE ㅜㅜ) 비둘기집의 원리에 의해 n>m인 경우는 무조건 가능하다고 처리하면 시간안에 계산 수 있다. i번째를 구할때 i-1만 알면 되므로 슬라이딩 윈도우를 써서 메모리 사용량을 줄일 수 있다. C 1<=n<=10^3인 n이 주어진다. 1<=x<=n인 어떤 x를 맞추기 위해 이 x가 어떤 y로 나눠지냐는 질문을 할 수 있다. 문제는 x를 맞추기 위해서 해야할 질문의 최소 수와 이때의 질문 순서이다. 소수를 구해나가면서 소수의 거듭제곱이 <=n 일 동안 답에 추가하면 된다고 한다. 다른 사람들은 이 방법으로 풀었는데 나는 와닿지 않았다 ㅜㅜ sqrt해서 소수판별을 해도 되고 에라토스테네스의 체로 미리 구해놓고 해도 된다. O(nloglogn) D 모름 E 모름
댓글
댓글 쓰기