34514번 - FFT
42번의 제출 끝에 드디어 맞았어요. (정답률이 저 때문에 정말 낮아졌어요)
처음에 프로필을 준다고 해서 시작했는데, 재미있으면서도 정말 힘들었습니다.
트리 문제가 알고보니 배낭 문제랑 엮인다는 점에서 신기했던 것 같아요.
다만 FFT를 풀면서 궁금한 점이 한 가지 있어요.
성공한 코드랑 실패한 코드의 차이점은 limit과 compare를 설정하는 것뿐인데요.
Limit을 75로 설정하여 너무 깊은 재귀를 막으려고 했는데도 TLE 코드는 엄청난 시간이 걸리더라고요.
반면에, 5로 나눠준 경우는 빠르게 처리하면서도 넓은 탐색을 할 수 있었고요.
코드 한 줄 차이가 시간을 좌지우지하네요...
그리고 저는 가장 적은 정점을 찾는 과정에서 정말 많이 노력했는데요.
여러분은 저처럼 힘든 과정을 거치지 마세요.
K가 1부터 10000까지일 때 정점의 개수를 출력한 파일을 올려드립니다.
줄 번호가 K랑 같아요.
node_count_from_1_to_10000.txt
(파일이 혹시 문제가 된다면 수정하겠습니다)
재밌는 문제입니다. 여러분도 시간 나면 도전해보셨으면 좋겠습니다.
댓글을 작성하려면 로그인해야 합니다.
hemisphere1357 1년 전 2
42번의 제출 끝에 드디어 맞았어요. (정답률이 저 때문에 정말 낮아졌어요)
처음에 프로필을 준다고 해서 시작했는데, 재미있으면서도 정말 힘들었습니다.
트리 문제가 알고보니 배낭 문제랑 엮인다는 점에서 신기했던 것 같아요.
다만 FFT를 풀면서 궁금한 점이 한 가지 있어요.
성공한 코드랑 실패한 코드의 차이점은 limit과 compare를 설정하는 것뿐인데요.
Limit을 75로 설정하여 너무 깊은 재귀를 막으려고 했는데도 TLE 코드는 엄청난 시간이 걸리더라고요.
반면에, 5로 나눠준 경우는 빠르게 처리하면서도 넓은 탐색을 할 수 있었고요.
코드 한 줄 차이가 시간을 좌지우지하네요...
그리고 저는 가장 적은 정점을 찾는 과정에서 정말 많이 노력했는데요.
여러분은 저처럼 힘든 과정을 거치지 마세요.
K가 1부터 10000까지일 때 정점의 개수를 출력한 파일을 올려드립니다.
줄 번호가 K랑 같아요.
node_count_from_1_to_10000.txt
(파일이 혹시 문제가 된다면 수정하겠습니다)
재밌는 문제입니다. 여러분도 시간 나면 도전해보셨으면 좋겠습니다.