목록2024/04 (18)
Binaryseop
https://www.acmicpc.net/problem/14502접근1. 재귀를 이용해서 3개의 벽을 세웁니다.2. BFS 또는 DFS를 이용하여 바이러스를 퍼트립니다.3. 안전 영역의 개수를 구합니다.4. 안전 영역의 최댓값을 구합니다. 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;class Virus { int r, c; Virus(int r, int c) { this.r = r; this.c = c; }}public class Main { static int n, m, maxSafeArea; static int[][]..
9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 접근 n이 최대 1,000,000이므로 이중 for 문으로 문제를 풀 경우 시간 복잡도가 O(n^2)이 되어 시간 초과가 발생합니다. 따라서 투 포인터 기법을 이용하여 시간 복잡도를 O(n)으로 줄여 문제를 해결해야 합니다. 풀이 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public c..
2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 접근 n이 최대 100,000, k가 최대 100,000일 때, 이중 for 문으로 문제를 풀면 시간 복잡도가 O(n * k)가 되어 시간 초과가 발생합니다. 따라서 슬라이딩 윈도우 기법을 이용하여 시간 복잡도를 O(n)으로 줄여 문제를 해결할 수 있습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public..
1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 접근 n이 최대 15,000이므로 이중 for 문을 이용하여 문제를 풀 경우 시간 복잡도가 O(n^2)이 될 것으로 예상됩니다. 따라서 투 포인터를 이용한다면 시간 복잡도를 O(n)으로 줄일 수 있습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; publ..