목록Data Structure & Algorithm/PS - JAVA (270)
Dev.baelanche
2 : 1 의 페어로 나가야 하므로 n/2 와 m 을 비교하여 큰쪽에서 인턴쉽에 나가게 한다. 출력할때는 n/2 와 m 중 작은쪽을 출력해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); for(int i=k; i>0; i--) { if(n/2 >= m) n--; else m--; } System.out.println(n/2 < m ? n/2 : m); } }
기본적인 이분탐색에서 한번 꼬아낸 문제이다. 각 랜선의 길이 : L 나눌 단위 길이 : D 일때, L / D 의 합이 K 를 만족하는 선에서 최대 길이를 구해야 한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); int n = sc.nextInt(); int a[] = new int[k]; for(int i=0; i
나무 자르기 문제와 거의 유사한 문제이다. 예산을 더하는 로직만 약간 다를뿐 이분탐색으로 접근하면 된다. 코드 1 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; long sum = 0; int max = 0; for(int i=0; i
이분탐색을 입문하기 좋은 문제이다. 예제로 풀이해보겠다. 나무의 높이는 20, 15, 10, 17 이고 최소값은 0, 최대값은 20이다. 최대값은 나무의 높이 중 가장 큰 것으로 해도 되고 문제에서 주어진 최대값 1000000000 을 사용해도 된다. low 20 15 10 17 high 0 20 정한 low, high 을 2등분 하여 조건을 성립하는 방향으로 범위를 좁혀가야 한다. 0과 20의 중간값은 10 이므로 10의 높이로 나무를 자른다. low 20 15 10 17 high 0 10 5 10 7 20 각 나무는 10, 5, 10, 7 의 길이만큼 남았고 자른 나무는 10, 10, 0, 10 으로 총 30이다. 나무는 적어도 7만큼 가져갈 것이므로 30은 너무 크다. 따라서 자를 높이를 올려야 하..
그래프에 대해 공부해 보았다면 DFS 로 풀 수 있는 문제란걸 유추할 수 있다. 연결된 정보를 가지고 문제를 푼다 -> 그래프 문제 만든 그래프로 최단거리, 최소거리를 구해야 한다 -> BFS 그렇지 않다 -> DFS 네트워크 연결이 한방향으로만 되지는 않을것이고 별도의 언급도 없으니 양방향 그래프라고 볼 수 있다. 2차원 배열로 그래프를 만들어 노드마다 연결된 노드 번호를 매겨주고 카운트를 세어주면 된다. 노드 탐색을 할때 연결된 노드를 전부 탐색한 뒤 재귀호출 하는 방식으로 구성하고 싶어서 큐를 이용했다. public class Main { static int n; static int a[][]; static boolean visited[]; static Queue q = new LinkedList(..
각 다리의 수에 따른 경우의 수를 이용하여 풀어야 한다. n / m 1 2 3 4 5 6 1 1 2 3 4 5 6 2 X 1 3 6 10 15 3 X X 1 4 10 20 n이 1일땐 m의 수만큼 경우의 수가 증가한다. n이 2일땐 m이 증가함에 따라 dp[n][m] = dp[n][m-1] + dp[n-1][m-1] 의 형식으로 증가하는걸 볼 수 있다. n이 3일때도 마찬가지이다. n이 1일때의 초기값과 n == m 일때의 초기값을 배열에 대입해주고 위 점화식을 이용하여 풀면된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long dp[][] = new long[30][3..
n 이 1일때 9 (1, 2, 3, 4, ..., 9) n 이 2일때 17 이다. 십의 자리수가 5일때 54 혹은 56 이어야 하므로 자리수 n 이 i, 일의 자리수가 j 일때 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 위와 같은 점화식을 얻을 수 있다. n이 2일때의 계단수가 17인 이유는 01 이 빠졌기 때문이다. 일의 자리수가 0일때는 제외해야 하므로 점화식에 추가해준다. if(j == 0) dp[i][j] = dp[i-1][j+1]; else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 마찬가지로 9일때도 90 같은 수는 만들 수 없으니 예외처리 한다. if(j == 0) dp[i][j] = dp[i-1][j+1]; else if(j == 9..
수열의 크기와 같은 크기의 dp 배열을 만들어 각 인덱스별로 최대값을 저장한다. 수열의 값 중 적어도 한 개를 선택해야 하고 연속적으로 사용해야 하므로, 이전 dp의 최대값 + 현재 배열의 값 / 현재 배열의 값을 비교하여 큰 것을 사용하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i