https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. Logic - 모든 버스 비용이 0보다 크거나 같다고 나왔기 때문에 다익스트라 알고리즘을 사용하여 풀이한다는 것을 유추할 수 있다. 일반 다익스트라 알고리즘과 동일하게 풀이하지만 해당 문제는 지나온 경로까지 표현해줘야 하기 때문에 경로를 추적하는 trace 배열을 한개 더 선언해주었다. trace배열로 경로를 찾는 과정 문제의 Testcase에서 내가 도출한 ..
알고리즘풀이
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1. Logic - 입력수가 10억을 넘기 때문에 입력만으로 시간복잡도가 터진다. 그래서 시간복잡도가 O(logN)인 자료구조인 priority_queue를 썼다. 그렇기 때문에 시간복잡도 log10억은 9이다. 작은 값부터 탐색해야 하기 때문에 priority queue에 greater인자를 넣어 오름차순으로 정리해주었다. 앞의 원소들 부터 차례대로 탐색하면서 1. 입력받은 수의 전체 합이..
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 1. Logic - 문제의 조건에 따라 왼쪽에서도 값을 넣고 오른쪽에서도 값을 넣다 뺏다하기 쉬운 자료구조는 deque가 적절하다. 연산을 최소로 하기 위해서는 구해야하는 수를 기준으로 오른쪽과 왼쪽 중 어디가 더 값이 적게 남았는지 체크를 해야한다. 덱에서는 큐와 다르게 인덱스로 값을 알 수 있기때문에 덱을 사용해서 풀이하며 된다. 2. Code #include using namespace ..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. Logic 비슷한 문제인 벽 부수고 이동하기 1(boj - 2206) 과 비슷하게 풀어보았다. 2206번 문제에서와 마찬가지로 vis배열 설정이 중요하다. 이번 문제에서는 부실 수 있는 블록의 갯수를 유동적으로 입력받기 때문에 BFS에서 처음 시작구간을 queue에 넣을 때 부실수 있는 block의 갯수를 입력받은 k만큼 넣어준 상태로 0이 될때까지 부셔나..
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. Logic - 입력을 받으면서 가장 큰 값과 해당 값의 인덱스 번호를 저장해놓는다. - 저장해 놓은 가장 큰 값의 인덱스를 기준으로 앞에서부터 인덱스까지 돌며 빗물이 찼을 때 가장 최댓값을 구하고 똑같이 뒤에서부터 인덱스 까지 돌며 최대값을 구한다. 이후 각 블록의 높이를 다 더한값을 최댓값에서 빼주면 빗물의 총량을 구할 수 있다. 14719번 문제가 어렵다면 2304 창고..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. Logic - 0에서부터 왔다가 돌아와서 책을 다시 가져가야 하기 때문에 모든 (경로값 * 2)를 하게된다. 그렇기 때문에 입력을 모든 값중 절댓값이 가장 큰 경로에 있는 책을 제일 마지막에 가져다 놓아서 * 2를 하지 않아야겠다는 생각을 했다. 1, 양수를 저장하는 positive배열과 음수를 저장하는 negative 배열을 받아서 각각 저장하며 절댓값을 통해 절댓값이 가장 큰 값을 저장해놓는다..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. Logic - 처음엔 dp테이블을 2차원이라고 생각했지만 인덱스 갯수가 1500000이기 때문에 dp table이 2개가 아닌 한개라고 생각했다. - 부분문제를 쪼개봤다 1. 해당 날짜의 상담을 할때 - idx + 상담에 필요한 시간 + 상담으로 받은 상담비용 2. 해당 날짜의 상담을 안할때 - 상담을 안하고 다음 인덱스로 넘어가기 2. Code #include using namespace std; int n; vector vec; int dp[1500001]; int solve(int cur) { if(cur == n) ret..
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 1. Logic - 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다. 최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘..
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. Logic 1. 주어진 정수 X를 조건대로 검사하며 조건에 맞게 재귀함수에 넣어 계산 한 후 임시 변수 next에 담는다. 2. 다음에 나올 값이 현재의 dp에 담긴 값보다 작아야 연산을 최소로 하기 때문에 해당 next값과 현재 ret 즉 지금의 dp[num]값과 비교를 해서 next값이 더 작다면 dp와 나중에 path를 출력해줄 before 배열을 갱신시켜준다. 2. Code #include using namespace std; int n; const int INF = 987654321; i..
