2018/06/25 썸네일형 리스트형 BOJ)11964 Fruit Feast 문제: icpc.me/11964 최대 포만감의 최대치가 t이고, 오렌지를 먹으면 a만큼 레몬을 먹으면 b만큼 포만감이 오를 때, 최대 포만감을 구하는 문제이다. 단, 조건이 하나 있는데 딱 한번 물을 마시면 현재 포만감을 반으로 줄일 수 있다. 현재 물을 마셨는 지 아닌지를 제약조건으로 둔다면 다이나믹 프로그래밍으로 문제를 해결할 수 있다. dp[i][j]= 포만감이 i이고 제약조건(물을 마셨는 지 여부)이 j일 때 상태의 존재 여부 12345678910111213141516171819202122232425#include #include #include using namespace std;int dp[5000005][2];int t,a,b,r;int main(){ scanf("%d%d%d",&t,&a,&.. 더보기 BOJ)11046 팰린드롬?? 문제: icpc.me/11046 길이가 최대 100만인 문자열 s가 주어질 때 s의 인덱스 l~r 까지의 부분 문자열이 팰린드롬인지 쿼리마다 출력하는 문제이다. n이 작다면 n^2의 방법으로 해결해줄 수 있지만 n이 크므로 manacher's 알고리즘을 이용하여 해결해주어야 한다. manacher's 알고리즘으로 전처리를 해준 뒤 중심으로 부터의 최대 팰린드롬 길이와 주어진 구간의 길이를 비교해주어 답을 출력해주면 된다. 시간 복잡도는 O(N+M)이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include #include using.. 더보기 BOJ)1222 홍준 프로그래밍 대회 문제: icpc.me/1222 문제를 해석하면 만약 홍준이가 팀원의 수를 k명이라 정했다면 학교 사람의 수가 k로 나누어 떨어지는 학교만 참가할 수 있다. 즉 주어진 수들을 전부 소인수 분해를 하였을 때 i를 소인수로 가진 학교의 개수를 a[i]라고 하면, a[i]가 2이상인 경우에서의 i*a[i]의 최댓값이 답이 된다. 하지만 모든 수의 소인수를 구할 경우 O(N*sqrt(N))으로 시간내에 들어오기에는 조금 무리가 있다. 하지만 수를 받으면서 소인수를 계속 연산하는 방법이 아닌 수를 전부 받아놓고 하나의 수에는 한번의 계산만 하는 방법으로 최적화 시켜 시간내에 통과시킬 수 있다. 이보다 좋은 방법은 모든 수 i에 대하여 자신을 소인수로 가지는 수를 직접 계산해주는 방법이다. 이 방법은 소스코드로 설명.. 더보기 이전 1 다음