전체 글 썸네일형 리스트형 BOJ)11585 속타는 저녁 메뉴 문제: icpc.me/11585 문자열 A와 B가 주어질 때 환형으로 이루어진 문자열 B로 이루어진 돌림판을 돌려서 A가 나올 확률을 구하는 문제이다. 우리는 환형으로 이루어진 문자열 B를 구현하기 위하여 문자열 B뒤에 문자열 B를 붙인 뒤 KMP를 이용하여 2개의 연속 된 문자열 B에서 A를 찾는 횟수를 구한 뒤 기약 분수 형태로 만들어 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #define MAX_N 1000000using namespace std;char a[MAX_N], b[2 * MAX_N];int n,.. 더보기 BOJ)4354 문자열 제곱 문제: icpc.me/4354 문자열 A가 주어질 때, A를 서로 같은 부분 문자열 N개로 쪼갤 수있을 때 N의 최댓값을 출력하는 문제다. 우리는 문자열이 N개의 부분 문자열로 쪼개질 때 규칙성을 찾아보면 KMP에서의 pi배열의 pi[a.length()-1]=(n-1/n)*a.length()를 만족한다는 걸 알 수 있다. 이를 이용하여 최대 N을 계산해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #include using namespace std;string a;vector pi;void getpi(){ pi.clear(); pi.resize(a.length()); i.. 더보기 BOJ)2233 사과나무 문제:icpc.me/2233 트리가 주어질 때 루트에서 DFS를 탐색하는 순서대로 0은 노드를 처음 방문할 때 1은 노드에서 더 이상 탐색이 불가능하여 return 될 때를 순서대로 수열로 나타낼 때 썩은 사과 2개를 동시에 제거 가능한 가장 가까운 노드의 0과 1의 위치를 출력하는 문제이다. 우리는 썩은 사과 2개가 주어질 때 동시에 제거 가능한 가장 가까운 노드를 LCA를 통하여 구할 수 있다. 0과 1로 이루어진 수열에서 0일 경우에는 노드를 추가하고 현재 보는 노드의 자식으로 설정 1일 경우에는 현재 보고 있는 노드의 부모를 현재 보고있는 노드로 설정해 주어 깊이와 부모를 구해준 후 LCA를 구해주면 된다. 12345678910111213141516171819202122232425262728293.. 더보기 이전 1 ··· 82 83 84 85 86 87 88 ··· 118 다음