문제 자연수 NNN이 주어졌을 때, AAA보다 크거나 같고, BBB보다 작거나 같은 수 중에서 NNN과 서로소인 것의 개수를 구하는 프로그램을 작성하시오. 두 정수를 나눌 수 있는 양의 정수가 111밖에 없을 때, 두 정수를 서로소라고 한다. 즉, 두 수의 최대공약수가 111이면 서로소이다. 111은 모든 정수와 서로소이다. 풀이 [A,B][A, B][A,B]에서 NNN과 서로소인 것의 갯수는 전체 개수에서 서로소인 것의 개수를 빼주면 된다. NNN과 서로소인 것은 NNN의 소인수 중 하나의 배수이면 된다. ...
5699번: 문자열 농장 문제에서 주어진 문자열을 트라이를 이용해서 저장해 두자. 그리고 아호 코라식을 이용해서 fail 노드까지 만들어 두자. 어떤 문자열 AAA가 다른 문자열 BBB의 이전 문자열 이기 위해서는 AAA가 BBB의 접미사 이거나 BBB... 예를 들어, an라는 문자열은 ant의 접미사를 이루고 있으므로 ant의 이전 문자열이다. ant라는 문자열은 cant라는 문자열의 이전 문자열이다. cant에서 t의 fail이 ant를 가리키고 있기 때문이다. ...
문제 길이 151515 이하의 NNN개의 문자열들과, 100010001000 이하의 자연수 KKK가 주어진다. N개의 문자열이 길이가 KKK... 문제 예제를 살펴보면 “ABA”, “CB”, “ABACB”가 주어지고 K는 7이다. 주어진 문자열은 최대 4번 등장할 수 있고, 예로 “ABACBCB”가 있다. “ABA”가 한 번, “CB”가 두 번, “ABACB”가 한 번 등장한다. 5905번: 악당 로봇 USACO ...
문제 준규가 계단을 오르내리는 운동을 U 와 D로 이루어진 문자열로 표현할 때, U는 계단을 한 칸 오르고 D는 한 칸 내려감을 나타낸다. 처음 위치를 000이라고 할 때, 계단의 위치가 음수가 되는 일은 없다. 또한 처음 위치와 도착 위치는 000으로 같다. 문자열의 일부가 주어질 때, 만들 수 있는 가능한 문자열의 모든 경우의 수를 1,000,000,0091,000,000,0091,000,000,...으로 나눈 나머지를 구하시오. ...