목록2024/04/22 (2)
Binaryseop
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..