안녕하세요-_-
이번 서울 리저널 발린 ;;;
08 뉴비 김상훈 입니다.
대회 전에 연습 때 부터 해결 하지 못한 질문인데 ;;; http://acm.pku.edu.cn/JudgeOnline/problem?id=3134 http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
아마 두 문제는 거의 비슷한 문제 인 것같은데요 ;;;
3134 번 문제의 경우 n 이 1,000 이라 백트래킹으로도 쉽게 ;; 답을 낼 수 있었는데
1945 번 문제는 n 이 20,000 이라 .,, 제 코딩 실력으로는(?!) 백트래킹으로는 도저히 답이 나올 생각을 안하는데요 ;;
....
1945 번 의 솔루션도 백트래킹이 맞는 건가요 ?!
실제로 status 를 보면 -_- 속도 / 메모리로 상위권인 사람들은 보니 대충 ...
DB 냄새가 나는데 ;;;
ㅠㅠ 고수님들의 답변 부탁드립니다.
아마도... 두 숫자로 표시할 수 있는 상태들에 대한 BFS를 하라는 이야기 인 것 같습니다.
(x, 31)로 갈 수 있는 상태들인:
(1, 32)
(1, 30)
(2, 29)
(2, 33)
등등...
공간복잡도는 O(N^2)가 되고, 시간복잡도도 마찬가지. 상태를 normalize(작은/큰 숫자가 앞으로 오게) 하면 절반으로 줄어듭니다
LucidaSH
안녕하세요-_-
이번 서울 리저널 발린 ;;;
08 뉴비 김상훈 입니다.
대회 전에 연습 때 부터 해결 하지 못한 질문인데 ;;;
http://acm.pku.edu.cn/JudgeOnline/problem?id=3134
http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
아마 두 문제는 거의 비슷한 문제 인 것같은데요 ;;;
3134 번 문제의 경우 n 이 1,000 이라 백트래킹으로도 쉽게 ;; 답을 낼 수 있었는데
1945 번 문제는 n 이 20,000 이라 .,, 제 코딩 실력으로는(?!) 백트래킹으로는 도저히 답이 나올 생각을 안하는데요 ;;
....
1945 번 의 솔루션도 백트래킹이 맞는 건가요 ?!
실제로 status 를 보면 -_- 속도 / 메모리로 상위권인 사람들은 보니 대충 ...
DB 냄새가 나는데 ;;;
ㅠㅠ 고수님들의 답변 부탁드립니다.
16년 전