구성적

【백준】- 24912. 카드 색칠

문제 https://icpc.me/24912 24912번: 카드 색칠 첫째 줄에 카드의 개수를 나타내는 정수 N이 주어진다. 둘째 줄에 N 개의 정수가 공백으로 구분되어 주어진다. i 번째 정수 ai는 i 번째 카드의 색깔을 나타낸다. 1, 2, 3은 각각 빨간색, 초록색, 파 www.acmicpc.net 아이디어가 간결하면서도, 떠올리기 쉽지 않았던 것 같습니다. 복잡하게 생각할 수록 더 안 풀리는 문제였다고 생각해요... 풀이 문제에 조건에 의하면 처음부터 색칠되어 있는 카드가 있을 수 있습니다. 처음에 색칠되어 있는 카드 중 서로 같은 색으로 칠해진 인접한 카드가 있는 경우, 그리고 없는 경우로 나누어서 생각해 봅시다. 처음부터 같은 색으로 칠해진 인접한 카드가 있는 경우 이 경우는 항상 불가능합니..

【백준】- 20921. 그렇고 그런 사이

문제 https://www.acmicpc.net/problem/20921 20921번: 그렇고 그런 사이 정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net 풀이 $N$ 이 최대 $4\;242$ 이기 때문에, $O(N^2)$ 와 $O(N)$ 의 시간복잡도의 풀이 모두 사용할 수 있습니다. 저는 두 방법 모두 설명해 보고자 합니다. 여러분은 어느 방식으로 푸셨나요? $O(N^2)$ 풀이 인접한 번호를 서로 교환해 보기 여기 사람들의 번호가 일렬로 나열되어 있습니다. 이 상태에서, 두 인접한 번호(오른쪽 번호가 더 큰)를 골라 서로의 위치를 바꾸었다고 가정해 볼게요. 과연 그렇고 그런 사이의 ..