문제 : boj1806
1. 틀린 방법
※ 제가 틀린 방법에 대해 써둔 것으로, 해설만 보고 싶다면 2번부터 보시면 됩니다.
덱에 모든 값들을 담으면서 그 합을 따로 계산한다. 그럼 일단 그 합은 최대치로 나올 수 있는 합이 될 것이다. 그 합이 S보다 작다면 0을 출력하고, 그렇지 않다면 합이 S보다 작아질 때 까지 덱의 시작부분과 끝부분을 각각 peek 해봐서 둘 중 작은 값을 덱에서 빼버린다. 이렇게 하면 그리디하게 답을 구할수 있을줄 알았다. 예를들어 S가 5일 때 다음과 같이 수행한다.
이렇게 짠 코드는 다음과 같다.
※ 틀린 코드임
...
int n = nextInt();
int s = nextInt();
int sum = 0;
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int cur = nextInt();
sum += cur;
dq.add(cur);
}
if (sum < s) {
System.out.println(0);
return;
}
while (!dq.isEmpty()) {
int st = dq.peekFirst();
int ed = dq.peekLast();
int pop = st>ed?dq.pollLast():dq.pollFirst();
if (sum-pop < s) break;
sum-=pop;
n--;
}
System.out.println(n);
...
그럴듯해 보였으나, 틀렸고 다시 생각해보니 문제는 시작 부분과 끝 부분의 값이 동일할 경우 사실 양측이 동일한 값이 나오지 않을때까지 더 살펴봐야 한다는 점이었다(동일한 것 중 뭘 제거하냐에 따라 이후에 제거할 수 있는게 다름). 그렇다고 동일한 숫자가 나올 때 마다 동일한 숫자가 아닐 때 까지 서로 빼거나 탐색하자니 10만개짜리에 전부 '1'만 입력으로 들어오는 그런 테스트케이스에 대해 유효한 시간 내에 통과할 수 없을 거라 생각했다. 그럼 기본 로직은 그대로 가져오고(그리디), 반대로 수행하기로 했다.
2. 풀이
'1'의 틀린 방법과 마찬가지로 그리디로 풀었다. 다만 '1'의 과정을 반대방향으로 할 것이므로 빈 덱에서 시작한다. 그리디 규칙은 다음과 같다.
A. 아직 합친 값(이하 SUM)이 S보다 낮다면 덱의 끝부분에 계속해서 입력을 받는다.
B. SUM이 S보다 높다면 덱의 시작 부분을 poll 한다.
위 둘을 반복하면서 중간중간 SUM이 S보다 높을 때 덱의 size 중 작은걸 기록해두면 그게 답이다. 종료 규칙은 덱이 비거나, n개를 모두 입력받은 상태에서 한번 더 SUM이 S보다 작아지는 경우이다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
private void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken())-1;
int s = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
Deque<Integer> dq = new ArrayDeque<>();
dq.add(Integer.parseInt(st.nextToken()));
int sum = dq.peekLast();
int answer = Integer.MAX_VALUE;
while (!dq.isEmpty()) {
if (sum >= s) {
answer = Math.min(answer, dq.size());
sum -= dq.pollFirst();
continue;
}
if (n == 0) break;
n--;
dq.addLast(Integer.parseInt(st.nextToken()));
sum += dq.peekLast();
}
System.out.println(answer == Integer.MAX_VALUE ? 0 : answer);
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
'PS > BOJ' 카테고리의 다른 글
백준 14467 자바 - 소가 길을 건너간 이유 1 (BOJ 14467 JAVA) (0) | 2022.01.25 |
---|---|
백준 20040 자바 - 사이클 게임 (BOJ 20040 JAVA) (0) | 2022.01.24 |
백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) (2) | 2022.01.22 |
백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA) (0) | 2022.01.21 |
백준 2467 자바 - 용액 (BOJ 2467 JAVA) (0) | 2022.01.20 |
댓글