You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
루트 땅의 번호는 1이며 어떤 땅의 번호가 K라면 왼쪽 자식은 2K, 오른쪽 자식은 2K+1이다.
오리들이 한 줄로 서있을 때 순서대로 원하는 땅을 가지도록 한다.
이미 점유한 땅은 지나가지 못할 때 각 오리가 원하는 땅을 점유할 수 있다면 0을, 도달하기 전에 점유된 땅을 만나 지나가지 못 할 때에는 막힌 점유된 땅의 번호를 출력하라
아이디어
처음에는 입력받은 모든 Q에 대해 DFS를 진행하면서 점유된 땅을 만날 경우 예외처리를 해서 풀었다.
하지만 최댓값을 생각했을 때 Q는 20만개이며 N은 약 10만개이다. 이러면 O(20만*10만)으로 시간 안에 풀이가 불가능하다.
먼저 시간 복잡도 생각하고 풀 걸 그랬다... 시간만 날렸네..
아무튼 다른 방법을 생각해야 하는데 도저히 모르겠어서 다른 사람들의 풀이를 봤다.
풀이를 보니 내가 제일 처음 생각했다가 당연히 시간초과나겠지 하고 넘겼던 풀이였다..
이진 검색 트리이므로 모든 Q에 대해 나누기 2를 해주면서 점유된 땅이 있는지 판단하면 된다.
이 때 Q는 총 20만개이고, 최대 10만의 수를 1까지 /2를 반복해야 하는데 이것은 이진 트리의 깊이와 동일한 값으로 약 log2(N)이 된다. 따라서 총 O(20만*log2(2^20)) = O(400만)으로 시간 안 풀이가 가능하다.
오늘의 교훈: 시간복잡도 계산 먼저 확실하게 하고 하자^ (범위가 클 때 특히!!))
구현
importjava.io.*;
importjava.util.*;
publicclassMain {
staticBufferedWriterbw = newBufferedWriter(newOutputStreamWriter(System.out));
staticBufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));;
staticStringTokenizerst;
staticintN, Q;
staticSet<Integer> banList;
publicstaticvoidinit() throwsIOException {
st = newStringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
banList = newHashSet<>();
for (inti = 0; i < Q; i++) {
func(Integer.parseInt(br.readLine()));
}
}
privatestaticvoidfunc(intdream) throwsIOException {
intcurrent = dream;
intans = 0;
while (current > 0) {
if (banList.contains(current)) {
ans = current;
}
current /= 2;
}
if (ans == 0) {
banList.add(dream);
}
bw.write(ans + "\n");
}
publicstaticvoidmain(String[] args) throwsException {
init();
bw.close();
}
}
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://www.acmicpc.net/problem/20364
문제 조건
아이디어
처음에는 입력받은 모든 Q에 대해 DFS를 진행하면서 점유된 땅을 만날 경우 예외처리를 해서 풀었다.
하지만 최댓값을 생각했을 때 Q는 20만개이며 N은 약 10만개이다. 이러면 O(20만*10만)으로 시간 안에 풀이가 불가능하다.
아무튼 다른 방법을 생각해야 하는데 도저히 모르겠어서 다른 사람들의 풀이를 봤다.
풀이를 보니 내가 제일 처음 생각했다가 당연히 시간초과나겠지 하고 넘겼던 풀이였다..
이진 검색 트리이므로 모든 Q에 대해 나누기 2를 해주면서 점유된 땅이 있는지 판단하면 된다.
이 때 Q는 총 20만개이고, 최대 10만의 수를 1까지 /2를 반복해야 하는데 이것은 이진 트리의 깊이와 동일한 값으로 약 log2(N)이 된다. 따라서 총 O(20만*log2(2^20)) = O(400만)으로 시간 안 풀이가 가능하다.
오늘의 교훈: 시간복잡도 계산 먼저 확실하게 하고 하자^ (범위가 클 때 특히!!))
구현
All reactions