Optimal Solution

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번째로 큰 수를 리턴하면 되지 않..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 분석 문제의 주인공은 미래의 주가를 예측할 수 있다. 그리고 그 예측이 항상 맞아떨어진다(부럽다). 문제의 주인공 홍준씨는 매일 3가지 중 하나의 행동을 한다고 한다. 주식을 하나 사거나, 원하는 만큼 가진 주식을 팔거나, 아무것도 하지 않는 것이다. 근데 홍준씨는 바보(?)라서 자신이 어떻게 행동을 해야 최대의 이익을 낼 수 있는지는 모른다. 그래서 우리는 홍준씨가 최대의 이익..