kthng

boj 1701 : editor(cube editor) https://www.acmicpc.net/problem/1701 내가 풀어낸 해법은 간단하다.하지만 좀더 빠르게 풀려면 뭔가가 필요한 것같다.. 접미사 배열에서 중복제거라던가..KMP라던가 ㅜㅜ 일단 내가 풀어낸 방법은1. 접미사 배열을 모두 뽑아낸다.2. 접미사 배열을 정렬한다.3. 인접한 접미사의 최대 매칭 길이를 구한다.4. 그 길이의 최대값을 출력한다. 2번->3번으로 넘어가는게 생각이 약간 필요하다.생각의 흐름은1. 접미사의 공통된 앞부분은 문자열의 공통된 부분문자열이다.2. 접미사는 정렬되어있다.3. i번째, i+1번째 접미사의 최장부분매칭길이를 구하면 공통된 부분문자열의 최대길이이다. 떠올릴 수 있는 간단한 방법이니만큼 어딘가에 개선의..

boj 2841: GITARA(외계인의 기타연주) https://www.acmicpc.net/problem/2841 문제를 이해하기가 힘들지만, 이해만 하면 풀 수 있는 아이디어를 간단히 떠올릴 수 있다. 7개의 stack을 이용하면 된다.stack의 top이 눌러야할 플렛보다 클경우 모두 pop해주고 눌러야할 플렛을 push해주면 해결된다. 7개의 줄은 모두 독립적으로 처리하면 된다. pop한 횟수와 stack에 push한 횟수만큼이 손가락을 움직이는 횟수이다.

boj 2934 : CVJETICI(LRH 식물) https://www.acmicpc.net/problem/2934 펜윅트리를 이용하여 해결할 수있다.울타리 기둥의 좌표가 주어졌을 때 그 울타리를 가로지르는 팬스의 갯수를 구하는 데 펜윅트리를 이용한다. 먼저 펜윅트리는 구간의 합을 빠르게 구하는 데 쓰인다. 이를 응용하면 좌표가 주어졌을 때 '그 좌표를 포함하는 구간들' 의 갯수를 빠르게 구할 수 있다. 울타리의 left, right가 주어질 때 add(left + 1,1), add(right,-1)이렇게 하면 해당구간을 가로지르는 펜스의 갯수를 누적할 수 있다. 이렇게 하면 sum연산으로 누적되어있는 울타리의 수를 알아낼 수 있다.그렇다면 남은건 이미 피어있는 꽃에 대한 처리는 어떻게해줘야하는가? 에대..