일단 분수를 분자, 분모입력값 쌍형태로 순서대로 n만개 입력받아.
그 분수들 중 두개를 더해서 나오는 분수값이 n만개중에 존재하면 그 순서쌍을 (첫번째 분수의 위치, 두번째 분수의 위치, 그 분수를 더한값과 같은 분수값이 있는 위치)를 구하는 문젠데
탐색시간이 너무오래걸려
그 분수들 중 두개를 더해서 나오는 분수값이 n만개중에 존재하면 그 순서쌍을 (첫번째 분수의 위치, 두번째 분수의 위치, 그 분수를 더한값과 같은 분수값이 있는 위치)를 구하는 문젠데
탐색시간이 너무오래걸려
아그리고 그씽은 여러개있을수있음
그 분수들은 중복없음? 그럼 해쉬로 하면 되는거 아닌가
중복있어도 해쉬로 할수 있을것 같은데
기본단위가 만임?
최대십만개있는거같은데
돌려보니까 대충 3만개쯤으로 짐작됨
분수들 중복있고 크기 순서없음
값범위부터 나눠서 검색시간을 줄일서 잇을거같은데
분수들 각각 더하는건 nC2니까 n*(n-1)/2번 아닌가 같은값이 있는진 해쉬로 찾으면 되고
후 다른사람들은 나랑 시간이 거의 500배이상차이나던데 왜그런거지
1. 분수값을 키로 하는 해쉬를 만들어서 다 넣음.값은 분수 위치(for n번)
메모이제이션
2.분수쌍 각각의 조합에 대해 더한걸 해쉬로 있는지 찾음(n^2/2)
이러면 n^2로 할수 있지 않나
지금은 뭘로 탐색했는데
n^2으로 풀 수 있는데 굳이 n^3할 이유가?