[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]
전국대회 예비소집 전 자기 전에 연습삼아 한 문제를 풀고 자려고 ‘화폐 개혁’이라는 문제를 선택했음.
열심히 풀다가 너무 안 풀려서 풀이를 보기로 했음.
T[i]를 ‘i를 최대 화폐로 사용할 때 사용하는 화폐의 수’로 정의해서 아래서부터 에라토스테네스의 체 방식을 이용하여 배수를 채워 나가는 Bottom-Up 방식과, T[i]를 ‘i를 최소 화폐로 사용할 때 사용하는 화폐의 수’로 정의해서 max값부터 내려오면서 그 값의 약수들을 채워나가는 Top-Down 방식의 풀이가 있었는데 Bottom-Up 방식은 글과 코드가, Top-Down 방식은 코드만 첨부되어 있었음.
Bottom-Up 방식도 잘 보면 이해할 수 있었을 것 같은데 첨부된 글이 너무 못 알아듣게 써 있어서 Top-Down 방식 코드를 보고 있었고, 마침 그 방식대로 짠 친구가 있어서 설명을 듣고 그대로 짰음. 처음에 풀이를 봤을 때는 저게 Bottom-Up 방식인지도 못 알아들었었음.
처음에는 Top-Down 방식으로 짰는데 전처리를 안 하고 그냥 
그래서 전처리를 이용해 소인수분해를 미리 해 두고, 계산할 때는 소수들을 이용해 약수를 직접 구하는 방식으로 코드를 고쳤지만 이번에도 마지막 테스트 케이스에서 TLE.
Top-Down 방식은 에라토스테네스를 이용하는 Bottom-Up 방식과는 다르게 약수를 구하는 과정에서 어쩔 수 없는 낭비가 생긴다는 것을 깨닫고, Bottom-Up 방식으로 다시 짜기로 함.
Bottom-Up 방식에서는 에라토스테네스 방식을 사용해서 시간복잡도가 
뭐가 문제일까 생각하다가, 설마 아니겠지 생각하면서도 나눗셈 연산과 퍼센트 연산이 느려서 그런게 아닐까 생각하게 됨.
a/i-(a/j+a%j/i) 이 부분을 a/i/(j/i)*(j/i-1)로 고치고 j가 i의 배수라는 사실을 이용해 a/j*(j/i-1)로 고쳐서 겨우겨우 AC.
나눗셈 연산과 나머지 연산 좀 줄인걸로 속도가 세 배이상 빨라졌음. 생각한 것 보다 나눗셈과 나머지 연산이 많이 느리다는것을 느끼는 계기가 되었음.
문제 자체는 평소에 잘 접하지 못하는 새로운 형태의 dp라서 좋았던 것 같음. T[i] 정의와 dp라는것만 떠올렸으면 스스로 풀 수 있었을 것 같은데 워낙 생소한 형태의 문제라 좀 고생했던 것 같음.
전국대회에서 좋은 결과 있으면 좋겠네요.