https://www.acmicpc.net/problem/20955그래프를 트리로 바꾸면 된다. 이때 사용할 수 있는 특성은 트리는 n개의 노드에 대해 n-1개의 간선을 가지며 사이클이 없는 연결 그래프이다. 처음 떠올린 풀이는 우선, 연결 요소들을 파악해서 sub graph로 나누고, 그 그래프를 트리로 만든 뒤 그래프끼리 잇는 간선을 추가하는 풀이였다. 그런데 문제를 보면 N, M이 굉장히 크다. 따라서 sub graph를 트리로 만드는 과정을 시뮬레이션 방식으로는 절대 불가능하다고 판단하고 연산 횟수만 구하면 된다는 점에 집중했다. 우리는 어떤 간선을 제거할지는 생각할 필요가 없고, 적절한 간선을 선택했다고 가정하고 제거하는 횟수만 구하면 된다. 그렇다면 그 횟수는 어떻게 구할 수 있을까? 일단, ..

20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 7 4 apple ant sand apple append sand sand ans : sand apple append 100,000개의 단어를 기준에 따라 정렬하면 된다. 우선 빈도를 저장해둬야 하는데 최대 O(n log n)으로 저장해야 하므로 맵에 저장을 했다. 그리고 기준에 따라 정렬을 해주면 되는데 우선순위 큐를 사용했다. 정렬 기준을 설정하는 건 항상 헷갈리는데 구조체에 () 연산자 오버..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 예제 4 2 3 1 5 2 4 1 ans : 18 4 3 3 4 1 1 1 1 ans : 10 문제를 잘 생각해 보면 기름 값이 가장 싼 도시를 3번 도시라고 하자. 그럼 3번 도시부터 목적지까지의 거리만큼 기름을 3번 도시에서 다 사두고 2번 도시를 다시 목적지로 두고 반복하면 된다. 이렇게 구현한다면 기름 값이 가장 싼 도시를 계속해서 갱신해야 하므로 우선순위 큐를 사용했다. 그리고 목적지를 갱신하는 방법은 좀 번거로워서 방문처리를 하는 방식을 ..

10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 예제 4 1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900 4 918 917 916..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 조건제한이 걸린 경로를 찾는 문제이다. 가장 먼저 떠올린 풀이는 dp [i][j]를 (i, j)까지 도달할 수 있는 경우의 수로 두고 네 방향 모두에서 (i, j)로 도달할 수 있으므로 4방향을 순차적으로 채우는 방법이었다. 이 방법은 아래와 같은 케이스를 잡아내지 못했다. 다음에 떠올린 방법은 DFS였다. DFS에서 백트래킹 느낌으로 메모이제이션을 떠올릴 수 있었다. 어떤 점 (i, j)에서 더 이상 갈 수 있는 곳이 없으면 (i, j)에 도달하면 바로 종료하는 방..

9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 예제를 좀 손으로 써보면 바로 규칙이 보인다. 완벽하게라는 말에 빠져들면 좀 돌아갈 수 있는데 그냥 간단하게 우선권이 상근이한테 있고, 두 명 모두 최대한 자기가 이길 수 있는 수를 둔다는 뜻이다. 돌이 5개 이하일 때는 바로 답이 보이므로 돌 6개부터 보자. 상근이가 처음에 돌을 1개 가져가면 창영이는 5개에 대해 게임을 시작한다. 상근이가 3개를 가져가면 창영이는 3개로 시작한다. 5개로 시작하는 경우 시작하는 사람이 이긴다. 3개도 마찬가지다. 규칙이 좀 보일 텐데 바로 일반화시켜 보자. k개로 상근이가 게임을 시작한다고 생각해 보자. 상근이가 1개 가져가면 창영이는 k-1개로..