[백준] 23564 - 재귀 문자열 by C++
https://www.acmicpc.net/problem/23564 23564번: 재귀 문자열 $(c, \{7\}), (cc, \{1,3\}), (ccc, \{1,1,1\})$ 등이 모두 정답이다. www.acmicpc.net 최근들어 제일 오래걸린 문제였다.... 오늘따라 머리가 안굴러가긴했는데, 그렇다보니 잘못된 방식 고집하면서 날린 시간도 너무 길었다. 아닌 것 같으면 다른 방식 생각해보는 습관도 가지자.... 알고리즘 방식 X1 = s1...s1 X2 = [s1...s1]s2...[s1...s1] X3 = {[s1...s1]s2...[s1...s1]}s3{[s1...s1]s2...[s1...s1]} X1, X2, X3를 각각 풀어서 작성하면 위와 같다. 이를 기반으로 X3를 통해 S, A 집합을 ..
2023. 1. 27.
[백준] 18870 - 좌표 압축
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 알고리즘 방식 간단히 예제를 통해 생각하면, [2, 4, -10, 4, -9] 내림차순 정렬과 중복 제거 후 전체 크기에서 현재 인덱스의 값을 빼주면 해당 인덱스의 좌표 압축 결과였다. 중복 제거는 헤더의 unique 함수를 통해 O(N)으로 구현할 수 있다. (unique 함수는 중복 제거된 벡터의 마지막 값을 iterator로 반환한다.) 따라..
2022. 12. 30.
