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번째 접미사의 최장부분매칭길이를 구하면 공통된 부분문자열의 최대길이이다. 떠올릴 수 있는 간단한 방법이니만큼 어딘가에 개선의..

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