목록알고리즘/백준 (341)
어흥
문제 링크: www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 1. 주의할 점 - 변수들을 헷갈리지 않도록 한다 - 초기화를 잘 처리해준다 - 특정 조건에 맞는 우선순위 큐를 사용하여 다음으로 태울 손님을 구한다 2. 구현 - 길에 대한 정보를 Arr[][] 함수에 저장한다 - 손님의 시작위치, 도착지점 위치를 P[][4] 배열에 담는다 - Need_fuel[] 배열에 대한 초기화를 수행한다. 해당 배열은 손님의 탑승위치..
문제 링크: www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - 스택 or 그리디를 이용하여 해결한다 - 본인이 생각한 특수 TC 이외에도 많은 특수 TC가 존재한다 ##일부 TC #1 6 2 391123 //output : 9123 #2 6 2 436436 //output : 6436 #3 7 3 7654321 //output : 7654 #4 6 2 362514 //output : 6514 #5 2 1 19 //output: 9 #6 7 2 9543543 //output: 9554 2. 구현 - String형태가 아..
문제 링크: www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1. 주의할 점 - 한명의 상사에겐 여러명의 직속부하가 있을 수 있다 - 칭찬을 모두 저장했다가 트리의 순서에 따라 부여한다 2. 구현 - 모든 직원들에 대해 상사->직속 부하에 대한 정보를 V[]벡터에 저장한다 - 입력받은 모든 칭찬에 대해 해당 직원의 index번호에 해당하는 Compliment[]에 더한다(한 직원이 여러번 받았을 수도 있으므로 할당이 아닌 더하기) - 사장인 1번부터 시작하..
문제 링크: www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 플로이드 와샬 알고리즘(시간복잡도: O(N^3)로 50^3 < 10^9)을 사용하여 구한다 - 간선들의 정보를 입력 받기 전, Dist[][] 배열을 1000으로 초기화한다 - 간선들의 정보를 입력받은 후, 플로이드 와샬을 통해 IJ 까지의 최소 간선 수를 구한다 - 1~N번까지의 사람들 중에서 가장 먼 ..
문제 링크: www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 1. 주의할 점 - BFS로 해결하도록 한다 2. 구현 - Check[][] 배열을 통해 음식물이 있는 좌표는 true로 갱신한다. 문제는 좌측 상단의 좌표가 (1,1)이므로 입력받는 좌표들에 대해 -1씩 한 좌표에 음식물을 표시한다 - 전체 Check[][] 배열에 대해 탐색을 시작하며, 음식물인 지점을 주변으로 4방향 탐색을 실시하여 음식물의 크기를 ..
문제 링크: www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 1. 주의할 점 - DFS를 통해 수행하므로, 갱신 + 원복을 잘 처리해야 한다 - 처리해야 하는 변수가 많아 헷갈릴 수 있으니 잘 정리하고 시작한다 2. 구현 - 8방향 탐색을 원활하게 처리하기 위해, 입력받을 때 각 물고기의 방향-1값을 저장한다 - 물고기의 정보를 Fish[]구조체에 담는다. 구조체는 행, 열, 진행방향으로 구성되어있다 - 현재 물고기의 위치는 Arr[][] ..
문제 링크: www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 1. 주의할 점 - 투 포인터를 이용하여 푼다. 매번 K개의 종류를 센다 -> TLE 2. 구현 - Arr[] 배열을 통해 연속된 K개의 초밥 중에 해당 종류의 초밥이 몇개 속해 있는지 나타낸다. Cnt를 통해 서로 다른 종류의 수를 나타낸다 - 벨트에 놓인 초밥의 종류를 Dish벡터에 담는다. 쿠폰을 사용하여 먹을 수 있는 초밥은 미리 표시한다. 동시에..
문제 링크: www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. 주의할 점 - 음수/0/양수로 나눈다 - 음수의 경우, 0과 관련지어서 생각한다 - 양수의 경우, 1일 때 조건을 추가한다 2. 구현 (이해가 안되는 부분은 코드에 주석을 달았으니 확인 바람) - 수를 입력 받을 때, 음수인 경우 M에 양수인 경우 P에 추가한다. 0인 경우, Zero++를 수행한다 - 음수의 경우 오름차순으로, 양수는 내림차순으로 정렬한 이후, 음수->0->양수 순서대로 A..