specidiee의 티스토리 블로그

[백준] 5525 (IOIOI)

문제 요약N+1개의 I와 N개의 O로 이루어져 있으며 I, O가 교대로 나오는 문자열을 $P_N$이라고 합시다.I, O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S 안에 $P_N$이 몇 군데 포함되어 있는지 구해야 합니다.N, M의 범위는 100만까지입니다.해설I, O로만 이루어진 긴 문자열(haystack)에서 특정한 문자열(needle)의 매칭 횟수를 선형 시간에 계산해야 하는 문제입니다. 그러한 문제를 일반적으로 해결하기 위한 여러 알고리즘이 있지만, 그것들을 몰라도 이 문제를 풀 수 있습니다.문자열을 왼쪽부터 순회하면서 첫 번째로 매칭되는 $P_N$을 찾습니다. 그 다음으로 매칭되는 $P_N$에는 첫 번째로 매칭된 $P_N$과 겹치는 부분이 있을 수도 있는데, 그렇다면 앞으로 다시 돌아가..

[백준] 31430 (A+B - 투 스텝)

문제 요약이 문제는 투 스텝 문제로, 한 번 채점할 때 프로그램을 2번 실행하는 형식입니다. 두 번의 실행은 서로 독립적입니다.첫 번째 실행에서는 음 아닌 정수 A, B가 주어지며, 소문자 알파벳으로 구성된 길이가 13인 문자열을 출력해야 합니다.두 번째 실행에서는 첫 번째 실행에서 출력한 문자열만 주어지며, A+B의 값을 출력해야 합니다.해설소문자 알파벳으로 구성된 길이가 13인 문자열만으로 두 정수의 합을 나타내야 하므로, 결국 문자열과 숫자를 서로 변환하는 문제를 풀어야 하는 것과 같습니다.소문자 알파벳은 26가지밖에 없는데, 13개를 쓴다면 $2\times 10^{18}$보다 작거나 같은 음 아닌 정수를 모두 표현할 수 있을까요? 다행히 $26^{13}$은 2,481,152,873,203,736,..