kthng

boj 2672 : 여러 직사각형의 전체 면적 구하기 https://www.acmicpc.net/problem/2672 풀었던 문제 중 제일 많이 틀렸습니다!! 인 것 같다.ㅜㅜ... 처음 접근은1. 사각형의 넓이를 다 더한다.2. 두 사각형이 겹치는 넓이를 뺀다. 이렇게였는데, 틀렸다.위와같은 방법으로 접근하려면 1.사각형의 넓이를 다 더한다.2. 두 사각형이 겹치는 넓이를 뺀다.3. 세 사각형이 겹치는 넓이를 더한다.4. 네 사각형이 겹치는 넓이를 뺀다.5. 다섯 사각형이 겹치는 넓이를 더한다..... 이와같이 접근해야하므로 시간복잡도를 감당할 수 없을 것 같아 포기. 생각을 거듭하다보면, 이런 생각을 떠올릴 수 있다. 위와같은 사각형이 주어졌을 때, 위와같이 영역을 모두 쪼갠다.이후 각 영역이 사각..

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