아이디어 고객들의 위치를 (a1, b1), (a2, b2), ... (an, bn) 이라고 하고 편의점의 위치를 (x, y) 라고 할 때 모든 고개들의 거리 합은 다음과 같이 정의할 수 있다. |x - a1| + |x - a2| + ... + |x - an| + |y - b1| + |y - b2| + ... + |y - bn| |x - a1| + ... + |x - an| 과 |y - b1| + ... |y - bn| 을 각각 x 에 대한 함수, y 에 대한 함수로 바라볼 때 각각의 함수는 기울기가 음에서 0 또는 양으로 바뀌는 변곡점을 가지게 되고 이 때의 값이 가장 거리합을 최소화 할 수 있는 값이다. a1 < a2 < ... < an 이고 ai < x 0 에서 n - 2i

아이디어 하나의 정점에서 다른 모든 정점으로의 최단 경로는 '다익스트라' 알고리즘을 통해서 구할 수 있다. 다익스트라 알고리즘은 다음과 같이 동작한다. 1. 시작점에서 다른 지점까지의 최단 경로를 표현하는 배열 dist 정의 2. 시작점 -> 시작점 : 0, 나머지는 INF 로 초기화 3. 아직 방문하지 않은 정점 중 가장 최소값을 갖는 정점 방문 4. 해당 정점에서 방문할 수 있는 정점들 갱신 5. 더 이상 방문할 정점이 없을 때까지 3 ~ 4 과정 반복 예제를 통해 보면 1, 2 과정을 통해 dist = [0, INF, INF, INF, INF] 가 된다. 3 에 의해서 1번 정점을 방문하고 1번에서 갈 수 있는 2, 3 을 갱신하게 된다. dist = [0, 2, 3, INF, INF] 아직 방문하..

아이디어 N-Queen 문제는 대표적인 백트래킹 문제다. 퀸의 공격 범위는 같은 행, 열, 대각선이므로 이를 고려해서 문제를 해결하면 된다. 1 ~ i-1번 퀸이 놓인 위치를 저장해놓고 i번 퀸을 놓을 차례 때 이전에 놓인 퀸들의 위치에 기반해서 같은 행이나, 열, 대각선이 아닌 곳이 존재하면 해당 위치에 i번 퀸을 놓고 다음 차례로 가는 것이다. 만약 존재하지 않는다면 i - 1 번째 퀸의 위치를 조정할 필요가 있는 것이므로 가능한 후보 중 다른 위치에 옮긴 후에 다시 탐색을 이어가면 된다. 2차원 배열을 만들어서 문제를 해결해도 되지만 이 문제의 경우 index 를 '열'로 간주하고 해당 index 에 '행'을 저장하는 1차원 배열만으로도 충분히 퀸의 위치를 표현할 수 있으므로 메모리 낭비를 줄이기 ..

아이디어 임의의 자연수 N 에 대해서 이게 제곱수들의 합으로 표현된다면 (N - 1) + 1 (N - 4) + 4 (N - 9) + 9 ... (N - X^2) + X^2 과 같이 다양한 방법이 있을 것이다. 따라서 dp[i] 를 i 를 제곱수의 합으로 표현할 때 그 항의 최소개수라고 정의한다면 아래와 같은 점화식을 얻을 수 있다. dp[i] = min(dp[i - 1], dp[i - 4], dp[i - 9], ..., dp[i - X^2]) + 1 1 ≤ X ≤ sqrt(i) 그리고 i 자체가 제곱수인 경우에는 dp[i] = 1 이 되어야 하므로 dp[0] = 0 으로 초기화 하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; ..

아이디어 임의의 K 원에 대해서 최소 인출 횟수가 M 보다 크면 K 가 너무 작다는 뜻이고 M 보다 작으면 K 가 너무 크다는 뜻이다. 따라서 K 원에 대해서 최소 인출 횟수를 계산해서 M 보다 크면 K 를 늘려가고 M 보다 작으면 K 를 줄여가는 방법을 사용하면 된다. 그리고 문제에서는 최소 금액 K 를 요구하고 있으므로 K == M 을 만족하는 케이스에서도 K 를 줄여가는 방식을 통해 K == M 을 만족하는 최소 K 를 구하면 된다. 추가로 현우가 주머니에 소지할 수 있는 금액의 최대값이 K 이므로 K 는 i번째 날에 이용할 금액들 중 최대값 이상이어야 한다. 그리고 인출 횟수인 M 의 최소값이 1이므로 K 가 가질 수 있는 최대값은 이용할 금액들의 합이되어 아래와 같은 범위를 가진다. max(이용..

아이디어 매번 다른 나무를 잘라야 한다면 나무들이 자라는 길이 Ai 가 가장 작은 것부터 순서대로 자르는 것이 가장 많은 양을 얻을 수 있는 방법이다. 다만 이 문제에서는 '같은 나무를 여러 번 자를 수 있다'고 하고 있다. 이로 인해 마치 매일 가장 높은 나무를 확인해서 이를 잘라가야 할 것처럼 보인다. 하지만 실제로는 같은 나무를 여러 번 자를 이유가 없다. 동일한 나무를 3번 자르든 2번 자르든 5번 자르든 1번 자르든 마지막으로 자르는 날만 동일하다면 그 나무로부터 얻을 수 있는 양은 동일하기 때문이다. 따라서 나무 A > B > C 가 있다고 했을 때 A 를 3번 자르는 방법은 C -> B -> A 로 자르는 방법에 비해서 C + B 만큼을 덜 얻게 되는 방법이므로 최대 양을 얻을 수 없다. 결..

아이디어 맨 위층을 1층, 맨 아래 층을 n 층이라고 할 때 dp[i][j] 는 위에서부터 시작해서 i 층 j 번째 숫자까지 선택했을 때 경로들의 합 중 최대값으로 정의한다. 그렇게 되면 아래와 같은 점화식을 세울 수 있다. dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + numbers[i][j] 이 점화식을 기반으로 문제를 해결하면 되고 i 번째 층에는 숫자가 총 i 개 있기 때문에 이 점에 유의해서 반복문을 잘 사용하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokeniz..

아이디어 배추흰지렁이 1마리로 인접한 배추들을 모두 커버할 수 있다. 따라서 (0, 0) ~ (N - 1, M - 1) 중 배추가 심어진 위치에서 dfs 를 수행해서 인접한 배추들을 탐색하도록 해서 dfs 가 총 몇 번 수행되는지를 세면 그것이 곧 최소 배추흰지렁이 마리 수가 된다. 이때 이미 dfs 를 수행해서 한 번 탐색한 위치에서는 또 dfs 를 수행하지 않도록 주의해야 한다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int M; static int N; st..