2014번: 소수의 곱 - 우선순위 큐 K개의 소수들을 중복을 허용하여 곱했을 때의 값들을 오름차순으로 나열했을 때,N번째 오는 수를 출력하는 문제이다. 가장 먼저 생각나는 방법은 수들을 정렬한 뒤 가장 작은 수를 제거하고,그 수를 이용하여 만들 수 있는 수들을 추가하여 정렬해주면 될 것이다.예제와 같이 수 2, 3, 5, 7을 이용하여 수를 만든다면처음에는 2를 제거하고 2*2, 2*3, 2*5, 2*7값인 4, 6, 10, 14을 추가해주며 정렬한다.그러면 3, 4, 5, 6, 7, 10, 14가 될 것이며 또 3을 제거한 뒤3*2, 3*3, 3*5, 3*7값인 6, 9, 15, 21을 추가하여 정렬해주면 될 것이다.원소를 추가/제거를 하면서 반복적으로 정렬을 해야하기에 우선순위 큐를 사용하면 효율적..
1351번: 무한 수열 - DP N, P, Q가 주어질 때,A[0] = 1A[i] = A[i/P] + A[i/Q]인 점화식을 만족하는 A[N]을 구하는 문제이다. 이와 같이 간단한 점화식은 중복되는 부분문제를 저장하는 DP기법을 사용하려고 접근하지만N이 최대 10^12이기에 부분문제를 저장하는 배열을 선언할 수 없다.그러나 점화식을 자세히 보면 i가 계속 P, Q로 나누어지는데P와 Q가 최소값인 2일 때에도 2^40 >= 10^12이기에 각각 40보다 많은 항을 보지 않는 것을 알 수 있다.이에 부분문제를 담는 배열을 지수에 대한 값을 인자로 두어dp[41][41]와 같이 표현한 뒤 점화식을 세워 문제를 풀 수 있다. 또다른 방법으로는 적은 값만 참조하기에 map을 이용하여value값이 0이라면 값을 업..
A - Death Note 한 페이지에 m개의 이름을 적을 수 있으며 매일 이름을 이어서 적을 때,하루마다 몇페이지를 넘기는 지를 구하는 문제이다.이전까지 이 페이지에 적었던 이름이 sum개, 이 날 적어야 하는 이름이 X개라면(sum + X) / m개의 페이지를 넘겨야 하며 마지막 페이지에는 (sum + X) % m개의 이름이 있다는 것을 알 수 있다.매번 sum값을 업데이트 해주며 (sum + X) / m값을 출력하면 풀 수 있는 문제이다. B - Segment Occurrences q개의 쿼리동안 문자열 s[l ... r]에 문자열 t가 몇 번 나타나는 지를 출력하는 문제이다.n, m이 10^3로 비교적 작기에 완전탐색으로 O(nm)에 문자열 s에서 t가 어느 인덱스부터 등장하는 지 찾아낼 수 있다..