코테

문제 링크 : https://www.acmicpc.net/problem/11404 문제의 이름이 플로이드인 만큼 플로이드-워셜 알고리즘을 사용하는 문제이다.플로이드 워셜 알고리즘은 모든 정점사이 간의 최단거리를 알아내는 알고리즘으로정점의 개수가 N 이라고 했을 때 시간복잡도가 O(N^3)인 알고리즘이다.따라서 플로이드 워셜 알고리즘을 사용하는 문제는 정점의 개수인 N이 작다는 특징이 있다. 우선 플로이드 워셜 알고리즘을 구현하기 위해 인접 행렬을 만들어주고값을 채워준다. 여기서 값이 의미하는 것은 arr[S][E] 는 정점 S부터 정점 E 까지 가는데 드는 최소비용이라는 의미이다.여기서 S와 E가 동일하다면 움직이지 않는것을 의미하기 때문에 0으로 초기화해준다. 그리고 3중 for문을 이용해서 위의 점화..

문제 링크 : https://www.acmicpc.net/problem/1744 위의 문제는 주어진 수열에서 수끼리 묶거나(곱하거나) 또는 그냥 더해서 최대합을 구하는 문제입니다.최댓값을 구하기 위해서는 양수에서는 가장 큰 값과 그다음으로 큰 값을 곱해서 더하는 게 좋지만 만약 해당 양수가 1일 경우에는곱하지 않고 그냥 더하는 게 더 큰 값이 됩니다. 음수에서는 내림차순으로 정렬하여 가장 작은 값과 그다음 작은 값을 곱해 더해줘야 합니다.양수와는 다르게 음수에서는 -1이라고 하더라도 무조건 음수와 곱해준 뒤 더해주는 게 더 큰 값을 더할 수 있습니다.이때 만약 같은 음수에서 짝지을 수가 없을 경우 0이 있다면 0과 곱해주는 것이 더 큰 값을 더할 수 있게 됩니다. 따라서 0보다 큰 양의 정수를 모은 pl..

문제 링크 : https://www.acmicpc.net/problem/1715 문제를 처음 접하고 예제 입력만을 가지고 단순히 생각해 보면 숫자 카드 묶음을 1차원 배열로 만들고 이를 오름차순 정렬해서 앞에서부터 더해 나가면 되지 않을까 생각할 수 있지만그건 오름차순으로 정렬하고 가장 작은 값들 2개를 골라 더한뒤 그다음 작은 값이 배열의 다음 값인 경우에만 가능하다예를 들어 문제의 예제처럼 10, 20, 40 일 경우에는(10 + 20) = 30 이고 해당 값 다음으로 큰 값이 40이기 때문에 단순 1차원 배열에서 오름차순 정렬로 풀 수 있다. 하지만 만약 주어진 카드 묶음이 10, 10, 10, 10, 10이라고 하면오름 차순 정렬 후 가장 작은 2개의 값은 10, 10 이기때문에 둘을 합치면 20..

문제 링크 : https://www.acmicpc.net/problem/1300 문제를 풀어서 보면 단순히 2차원 배열의 값들을 1차원 배열로 옮겨서 오름차순으로 정렬한 뒤K번째 인덱스(1부터 시작)의 값을 출력하면 되는 문제다. 하지만 N의 값이 최대 10^5 이기 때문에 이를 2차원 배열 N*N으로 만든다면 최대 10^10 개의 값들이 생성된다.따라서 단순히 2차원 배열의 값을 1차원 배열로 옮겨서 해결할 수는 없다. 따라서 다른 풀이를 생각해야 한다.먼저 문제 조건에 따라 3 * 3 배열을 1차원 배열로 전환하고 오름차순 정렬하면1 2 2 3 3 4 6 6 9가 되는 것을 알 수 있다.이때 K번째 인덱스의 값은 절대 K값 이상이 될 수 없다는 것을 알 수 있다. 따라서 K번째 인덱스의 최댓값은 K,..