어떻게 이분탐색으로 해야할 지 감이 안왔던 문제근데 되돌아보니 수업 때 11122233345 이런식으로 예시를 보여주셨던게 생각났다... 아..! 먼저 완전탐색으로 다 보면 n*n = 10^5라서 볼 수 없다 최적화를 해야되는데 ..1에서 n*n까지 이분탐색을 한다? -> 이분탐색으로 뭘 어떻게 할건데? 만 생각났었다. 이분탐색으로 값의 범위를 줄여가면서 이분탐색으로 찾은 중간값(mid) 이하인 숫자가 몇 개 있는지 찾으면 된다. 이 때 중간값(숫자)보다 m이 더 크면 중간값은 답이 될 수 없고 무조건 중간값 + 1이어야 한다.중간값(숫자)보다 m이 작으면 답은 중간값이 될 수도 있고 그 밑에 값이 될 수도 있고 .. 그러하다. 이때 mid - 1을 해준다. 아 어렵다.
알고리즘/백준
완전탐색을 생각해봤다. 각 세사람이 가지고 있는 수를 가지고 만들 수 있는 경우가 1000 * 1000 * 1000으로 10억이 되어서 시간 초과가 난다는 것을 발견했다. 최적화를 어떻게 해야할까?세 수가 똑같을 경우 0으로 가장 작다.두 수가 같고 1차이 나는 수가 있으면 1로 작다.세 수가 모두 다르고 가장 큰 수와 가장 작은 수가 2 차이나면 2로 작다.세 수가 모두 다르고 가장 큰 수와 가장 작은 수 가 3 차이나면 3으로 작다.... 세 사람의 각 수를 비교해야한다. 근데 이걸 반복문으로 비교할 생각밖에 안났다. 아무리봐도 그건 아닌데 어떻게 해야하지?무엇인가 비교할 때 for문에 갇혀있지 말 것 ,, for문 말고 while문을 활용해서 반복문을 쓰되 종료조건을 설정하면 된다. 세개의 배열..
