Optimal Solution

https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 문제 분석 a와 b로만 이루어진 문자열이 있다. 이 문자열에서 a가 모두 연속이 되게 하기 위해 a와 b의 위치를 교환할 것인데, 이 때 교환 횟수의 최솟값을 구하는 것이 문제이다. 이 문자열은 원형이라서, aabbbba 역시 a가 모두 연속되어있다고 할 수 있다. 처음에는 사실 문제를 이해하지도 못했다. 문제에선 그저 교환이라고만 되어있어서, 나는 이게 b라는 문자를 a로 바꿀 수 있다 라는 의미의..

https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제 분석 더욱 최적의 해가 있겠지만, 일단은 무식한 완전 탐색으로 풀었다. 빨간/파란 공을 왼/오른쪽에 모을 수 있다. 이 때, 공을 이동할 횟수는 이렇다. 만일 빨간 공을 왼쪽으로 모은다면, 공을 이동하는 횟수는 가장 왼쪽에 모여있는 빨간 공을 모두 제거한 후 남은 빨간 공의 개수 이다. 왜냐, 이미 왼쪽에 모여있는 빨간 공은 굳이 건드릴 필요가 없기 때문이다. 그..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 문제 분석 고속도로가 있는데, 고속도로에도 지름길이 있다고 한다(그럼 왜 고속도로지 ?). 아무튼간에, 고속도로를 최단 거리로 주파하고 싶은 문제 속 '세준이' 를 위해 고속도로 출발지점(0)부터 도착지점(D)까지, 지름길을 타든 말든간에 최단 거리가 몇인지를 구해줘야 한다. 어떻게 보면 경로에 가중치가 있기 때문에 다익스트라를 사용할 수도 있을 것 같다는 생각을 가장 먼저 하긴 했는데..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 문제 분석 전형적인 DP 문제같아 보인다. 1만 이하의 정수 N을 1, 2, 3의 합으로 나타내는 방법이 총 몇 가지인지를 구하는 것이고, 전체 경우의 수를 구할 때는 순서를 따지지 않는, 즉 순열이 아닌 조합의 개수를 묻는 문제이다. 문제에서 예시로 제공한 케이스를 살펴보면, N = 4일 때는 아래와 같은 경우의 수가 나온다. 4 =..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제 분석 크기가 N인 어떤 수열이 주어진다. 이 수열의 연속 부분 수열 중 가장 긴 연속 부분 수열의 길이를 구할 것인데, 연속 부분 수열의 조건은 연속 부분 수열을 이루는 숫자 중 같은 숫자가 중복해서 나와도 되지만 K개 이하로 나와야 한다는 것이다. N은 최대 20만이다. 따라서 완전 탐색으로 접근 시 O(N^2)이 소요되므로 시간 초과가 날 가능성이 있다. 따라서 이를 최대한 줄여야 ..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 분석 설명을 길게 해야되는지 잘 모르겠지만, 너무나도 흔한 BFS 문제이다. 흔히 그래프 문제에서 최단거리를 구하고자 할 때 BFS나, 이를 더 발전시킨 다익스트라 등을 사용하곤 하는데 여기서는 매우 간단한 BFS로도 풀 수 있다. 코드 #include #include #include using namespace std; struct Positio..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 문제 분석 N명의 사람이 정해진 순서대로 줄을 선다. 그런데 각 사람들은 자신의 키보다 큰 사람이 왼쪽에 몇 명 있는지를 알고 있다(전체 순서는 따로 공개된 게 아니고). 그리고 각 사람들의 키는 1 ~ N 사이이고, 중복이 없다. 예시를 보자. 4명의 사람이 있고, 각 사람의 키는 1, 2, 3, 4이다. 이 때, 각 사람들이 알고 있는, 자신의 키보다 큰 왼쪽 사람의 수는 각각 아래와 ..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 분석 N X N 크기의 표에 수가 N^2개가 채워져 있는데, 이 표에는 특징이 있다. 바로 모든 수는 자신의 한 칸 위의 수보다 크다는 것이다. 이 표가 주어졌을 때, 이 표에서 N번째로 큰 수를 찾아야 한다(다행히 표에 채워진 수는 모두 다르다). 처음 봤을 때는 문제가 매우 쉽다고 생각했다. 그냥 N X N 배열을 만들고, 배열에 수를 입력받은 후 정렬한 다음 N번째로 큰 수를 리턴하면 되지 않..