백준

【백준】- 24912. 카드 색칠

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

【백준】- 13141. Ignition

문제 https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 발상이 신기해서 재밌게 풀었습니다. CLASS 6을 찍기 위한 마지막 문제이기도 했고요! 그래서 그런지 이 문제만은 꼭 풀이로 남겨보고 싶었습니다. 풀이 최단 거리를 이용하여 푸는 문제라는 것을 떠올릴 수는 있겠지만, 정점이 아닌 간선에 대한 정보를 물어보고 있는 데다가, 그것도 가장 빨리 불타는 간선도 아닌 가장 마지막에 타는 간선에..

【백준】- 16341. Horsemeet

문제 https://www.acmicpc.net/problem/16341 16341번: Horsemeet Traditional games such as chess or checkers, with slight modifications are also played in Binary Casino. However, not many people play them, as these games are often referred as boring. The visitors are more attracted to more dynamic games which cause adre www.acmicpc.net 문제를 간단히 요약하면... 두 나이트가 $8 \times 8$ 내의 체스판에서 정해진 위치에 놓여 있고, 백부터 시작..

【백준】- 14263. 카드 놓기

문제 https://www.acmicpc.net/problem/14263 14263번: 카드 놓기 영선이는 카드와 그리드를 가지고 놀고 있다. 각각의 카드는 직사각형 모양이며, 색칠되어져 있다. 두 카드가 같은 색을 가지는 경우는 없으며, 크기도 카드마다 다를 수 있다. 영선이는 한 번에 www.acmicpc.net 풀이 카드가 쌓여 있는 관계를 잘 나타낸다면 방향성을 가지고 있는 그래프로 나타낼 수 있고, 위상 정렬로 풀 수 있게 됩니다. 아래와 같이 카드가 놓여 있다고 해 볼게요. 카드 $A$ 와 $D$ 는 처음부터 놓을 수 있습니다. 카드 $B$ 는 카드 $A$ 와 $D$ 가 놓여야 놓을 수 있습니다. 카드 $C$ 는 카드 $A$ 가 놓여야 놓을 수 있습니다. 카드 $E$ 는 카드 $B$ 가 놓여야..

【백준】- 23545. Liquid Cats

문제 본 문제는 외국어 문제이기에, 제가 문제 번역을 작성해 두었습니다. 아래의 링크를 참고해 주세요! https://www.acmicpc.net/board/view/108204 글 읽기 - 【번역】23545. 고양이 액체설 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 좀 발 번역이라... 죄송합니다. 간단하게 요약하자면, 덩어리 하나를 격자의 아래쪽에 최대한 쑤셔 넣고, 그때의 덩어리가 차지하는 높이가 최소가 되려면 어떻게 해야 할지 생각해 보아야 하는 문제입니다. 풀이 단순히 아래쪽 칸부터 채워나갈 수 있다면 좋겠지만, 고양이의 몸이 둘로 분리될 수 있기에 아래쪽 칸을 채우지 않는 경우가 최적일 수도 있습니다. 아래의 예시의 경우, 고양이가 $4$ 칸을 차지한다고 했을 때, 왼쪽..

【백준】- 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)$ 풀이 인접한 번호를 서로 교환해 보기 여기 사람들의 번호가 일렬로 나열되어 있습니다. 이 상태에서, 두 인접한 번호(오른쪽 번호가 더 큰)를 골라 서로의 위치를 바꾸었다고 가정해 볼게요. 과연 그렇고 그런 사이의 ..

【백준】- 14515. Yin and Yang Stones

문제 본 문제는 외국어 문제이기에, 제가 문제 번역을 작성해 두었습니다. 아래의 링크를 참고해 주세요! https://www.acmicpc.net/board/view/104727 글 읽기 - 【번역】14515. 음양 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 풀이 문자열 $S$ 의 길이가 최대 $100,000$ 이기에, 돌을 선택하는 모든 방법을 일일이 모두 따져보는 방법은 너무 시간이 오래 걸리게 됩니다. 돌을 하나만 선택할 수 있다고 가정해도 그 가짓수는 무려 $100,000 \times 99,999 \times ... \times 2 \times 1$ 가지나 됩니다. 그 대신, 우리가 할 수 있는 연산에서 규칙을 찾아 봅시다. 검은색 돌을 흰색 돌보다 $1$ 개 더 많도록 연..

【백준】- 22151. Игра

문제 본 문제는 외국어 문제이기에, 제가 문제 번역을 작성해 두었습니다. 아래의 링크를 참고해 주세요! https://www.acmicpc.net/board/view/101822 글 읽기 - 【지문 재작성】22151. 룬석 옮기기 게임 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 풀이 게임을 먼저 시작하는 알파가 이동 한 번으로 룬석을 정해진 위치로 옮길 수 있는지, 없는지에 따라 상황을 나누어서 생각해 봅시다. 이동 한 번으로 정해진 위치로 옮길 수 있는 경우라면, 거리가 $m$ 이하인 경우겠죠. 1. 한 번에 옮길 수 있는 경우 한 번에 정해진 위치로 옮길 수 있다면, 당연히 옮기는 것이 최선의 전략입니다. 게임은 알파가 항상 승리하게 됩니다. 2. 한 번에 옮길 수 없는 경우 ..