22/12/04 PS

-@yunny_world & *s3..g3 & s#100..

 

앞으로 가능한 자주 solved.ac에서 위와 같이 문제 뽑아서 1시간 동안 푸는 연습을 해야겠다. 

 

BOJ 23057 도전 숫자왕(S2)

문제 요약:

N개의 숫자 카드 합보다 작거나 같은 수 중, 카드에 적힌 수의 합으로 만들 수 없는  수의 개수를 구하자.

 

풀이:

N <= 20이니 O(2^N)의 브루트포스로 해결 가능하다. 

카드에 적힌 수의 합들을 set으로 관리한 후 전체에서 set에 들어있는 수의 개수를 빼주면 답을 구할 수 있다.

 

BOJ 1497 기타콘서트(S2)

문제 요약:

N개의 기타가 M개의 곡 중 전체 또는 일부를 연주할 수 있을 때, 최대한 많은 곡을 연주할 때에 필요한 기타의 최소 개수를 구하자.

 

풀이:

N <= 10이니 O(N^3)의 브루트포스로 해결 가능하다.

i개의 기타를 골랐을 때 연주할 수 있는 곡을 관리하기 위해서 비트마스킹을 이용하면 편하다.

 

BOJ 17425 약수의 합(G4)

문제 요약:

f(x) = x의 모든 약수의 합,  g(x) = 1 ~ x의 모든 자연수의 f값의 합이라고 할 때, 쿼리마다 N이 주어지면 g(N)을 출력하자.

 

풀이:

g(x)를 미리 전처리 해두어, O(T)만에 해결할 수 있다.

g(x) =  g(x - 1) + f(x) 이므로 g는 f를 구한 이후 누적합을 이용하면 된다.

f는 에라토스테네스의 체로 구하면 된다.

 

여담으로 에라토스테네스 체 문제 풀 때, 약수를 구하는 것보다 배수를 구하는 것이 쉽다는 말을 알게 되니 기억하기 더 쉬워진 것 같다. 

 

(20min, AC) A번는 처음에 입력 받는 부분이 계속 초기화 되어서, 시간 걸린게 아쉽다.

(41min, 1WA, AC) B번 문제는 문제를 제대로 안읽고, 모든 곡을 연주할 때에 필요한 최소 개수를 구해서 한번 틀렸다.

(61min AC) C번 문제는 A, B에서 시간을 필요 이상으로 잡아먹어서, 60분 안에 못 푼게 아쉽다.

---

BOJ 23271 Grazed Grains(G4)

문제 요약:

n개의 원들이 주어질 때, 그 원들이 이루는 넓이의 합을 구하자.

 

풀이:

범위가 매우 작고, 오차 범위가 매우 크다. 

특정 넓이에 대해서, 랜덤 좌표를 1e6개 정도 만들어 n개의 원들 안에 포함되는 좌표의 비율을 이용해 전체 넓이 * 비율로 답을 구할 수 있다.

 

처음에 코사인 법칙 쓰고, 겹치는 부분 빼고 별 이상한 기하적인 접근 했는데, 다 반례들이 있었다. 문제에서 상대오차가 10%인 것을 보고 무작위화 알고리즘 써야하는 걸 눈치 챘어야 한다. 상대 오차 10%가 수상하긴 했는데, 그 다음 생각을 못한 것이 아쉽긴 하다.