https://www.acmicpc.net/problem/1348문제조건R x C 모양의 주차장N개의 차와, M개의 주차 구역차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하시오.접근방법 단순하게 BFS를 이용해서 탐색하면 되는 문젠줄 알았는데, 전혀 그렇게 풀리지 않는다. 일반적인 구현문제가 아니라 특수한 알고리즘이 필요한 문제다,,,  Bipartite matching 이분매칭이라는 알고리즘이 필요하다. 주차구역과 차를 연결해주면서 짝을짓고, 짝을 짓는 경우의 수에 따라 최솟값을 비..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제조건 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이는? 접근방법 시간제한도 타이트하고, 입력값도 크게 주어지길래, 단순히 for문 두번 돌려서 O(n^2) 으로 시간이 걸리게 된다면 당연히 시간초과가 날 것이라고 생각했고, 문득 저번에 이런 비슷한 문제를 푼 경험이 떠올랐다. 2024.03.21 - [Algorithm/구현, 시뮬레이션..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제조건 두개의 전봇대가 있고, 서로 교차하지않게 전깃줄이 이어지도록 하는 경우일때의 제거해야할 전깃줄 개수와 A전봇대에서의 제거되는 번호 같은 위치에 두개이상의 전깃줄이 연결될 수는 없다. 완전탐색으로 풀려고 시도하면 전깃줄으 개수가 10만개이므로, n^2는 시간초과가 날 것이다. 따라서 어떤 접근법으로 가면 시간을 단축시킬수 있을까 생각해봤다. 이진탐색으로 접근하는 방법인데 다행히도, al..

https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 문제조건 N개의 줄에 각 칭호의 이름과 칭호의 상한 값이 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다. 처음 봤을때 너무 쉬워서 빠르게 구현부터했다. #include..

https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 구슬 N개를 그룹 M개로 나눈다. 각 그룹은 무조건 구슬이 1개이상이다. 모든 경우의 그룹을 나눴을때, 그룹의 최대값이 나올 수 있는 경우의 수 중 최소일때를 찾는다. 접근 방법이 도저히 떠오르지 않았다. 각 경우의 수를 모두 구해야하는 완탐으로 접근해야 하나,,? N이 늘어날수록 어마무시하게 시간복잡도가 높아질게 뻔히 보이므로 알고리즘적으로 접근방법을 찾아야만 한다,,, 진짜 모르겠다 멍..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다.라는 조건에서 첫 번째 생각은 총 N일동 안 자신이 사용할 금액 중 가장 큰 값 이상이어야 문제조건 자체가 성립된 다는 것이다. 당연한 말인 게 남은 금액을 통장에 집어넣기 때문에 만약 사용할 금액 중 가장 큰 값보다 작다면, K원 인출, K원 집어넣기 무한반복 ,,,,,,, 이렇게 첫 번째 조건은 만족한 것 같고, 두 번째로는 정확히 M..