https://www.acmicpc.net/problem/27438
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net백준 27438
영화감독 숌 2
시간 제한 0.5초에 1<=N<=13,559,699이고 '종말의 수'라는 조건을 만족하는 N번째 수를 찾는 거임.
N이 작을 때는 걍 1<=i<=약간 큰 숫자 반복문 돌리면서 브루트포스로 종말의 수 조건 만족하는지 풀면 됨.
N이 존나 클 때는 이런 저런 방법이 있음.
전자가 영화감독 숌 1 실버5고 후자가 영화감독 숌 3 플래티넘4
지금 거는 애매한 N과 골드 4의 난이도임. 태그는 브루트포스, 런타임 전의 전처리 이렇게 딱 2개 달려있음
근데 도저히 모르겠다. 이거 6시간 붙들고 있는데 도저히 모르겠다. 푼 사람 20명 정도라 인터넷에 정보도 없고 그나마 찾은 건 내 눈엔 선결문제요구의 오류마냥 또 다른 문제를 제시하더라.
전처리라길래 로컬에서 10분 들여서 13,559,699개 전부 배열 형식 맞추고 txt파일로 출력저장해서 그대로 백준에 복붙하는 것도 시도는 해봤는데 이렇게 하면 소스코드 용량이 300메가가 되더라. 백준에 안 올라감ㅋㅋ
제발 좀 도와줘라...... 잠이 자고 싶다.....
https://www.acmicpc.net/problem/27438
댓글 기다리다가 울면서 잠 든다ㅜㅜ 내일 아침에 다시 글 볼게
666 이 연속으로 들어가야 하니까 앞+666+뒤 브루트포스로 ㅈㄴ 조진다음에 힙에다 넣고(중간에 visited 으로 중복 거르고) n 받은다음에 n만큼 pop해서 결과 출력하면....시간초과 나려나.... 아님 수열 규칙성을 찾아야 할 것 같은데...음... 정 안되면 그냥 숀 3 풀이 이해하고 써먹는게 맞는듯 하다 ㅇㅇ
골드5따리인데 아이디어 남겨봄 첨엔 너가말한거처럼 전부다 계산하고 파일에서 읽어오는거 생각했는데 그건 아니라고 하고 그렇다면 너가 계산한 텍스트 보면서 n범위에 따른 수를 전부 적어놓는거임
그래서 13,000,000 이란 숫자를 범위를 나누는거임 1~1000/1001~2000/2001~3000/... 이렇게해서 미리 1, 1001, 2001일때의 값을 적어 놓은뒤에 입력에따라 범위를 나누고 1000개정도는 돌려보는거임
숌1에서 10000개정도로 했을때 50ms걸리니까 0.5초면 음 한 5만개나 10만개 정도 해도될거같은데? 1일때 숫자 100001일때 숫자 200001일때 숫자 ... 13500000일때 숫자 이렇게한다음에 다돌려보는거 어떰?
그렇게하면 어떤수가 들어와도 결국 10만개 안으로 브루트포스 가능할것같다 이것이 내생각임
맞네. 고맙다. 지금은 플레티넘 숌 3 보고있음.