백준/탐색 (11) 썸네일형 리스트형 백준 1174 - 줄어드는 수 https://www.acmicpc.net/problem/1174 문제의 조건은 숫자가 줄어들기만 하면 되기 때문에 탐색이 간단한 편임을 눈치챌 수 있다. "9876543210"에서 순서대로 몇 개의 문자를 선택하면 그것이 줄어드는 수이므로 $ 2^{10}$번의 연산으로 모든 경우의 수를 확인할 수 있다. 적당한 방법을 통해 줄어드는 수를 모두 구한 후 답을 출력해 주자. 정답 코드 - C++1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#pragma GCC target("avx,avx2,fma,bmi,bmi2,lzcnt,popcnt")#pragma GCC optimize("O3.. 백준 9825 - MODSUM https://www.acmicpc.net/problem/9825 문제를 보면 다음과 같이 언급하고 있다. Important note: You can assume that the result will always be less than 1,000,000. 이 말을 통해 문제에서는 연산의 제한이 $10^{6}$임을 암시하고 있다. 문제에서 제시한 계산식 \[\sum_{x_1 = v_1}^{w_1}\sum_{x_2 = v_2}^{w_2} \cdots \sum_{x_n = v_n}^{w_1} f(x_1, \dots, x_n)\] 으로만 보면 많은 연산이 필요할 것으로 보이나, 제한을 걸고 있기 때문에 안심하고 브루트포스를 해도 되는 것으로 이해할 수 있다. 문제의 제한을 이해했으므로 나머지는 신경 쓸 필요.. 백준 1522 - 문자열 교환 https://www.acmicpc.net/problem/1522 힌트 더보기 특정한 상태를 만들어 보는 방법을 생각해보자. 그리고 원형의 상태가 문제 풀이에 어떤 영향을 미치는지도 생각해보자. 풀이 더보기 우리는 aaaabbbb 꼴과 같은 상태를 만들어 볼 것이다. 그러면 왼편의 b는 오른편의 a와 바꿔야 할 것이다. 물론 원형이라는 조건 하에 abbbbaaa 같은 문자열도 성립됨을 상기하자. 다만 abbbbaaa를 만드는 것과 aaaabbbb는 구현상 모순이다. 우리는 이 모순을 극복하기 위해 원형이라는 점을 이용해 문자열을 쉬프트 할 것이다. 그러면 문제는 다음과 같이 바뀐다. "원본 문자열을 x번 쉬프트 한 상태에서 aaaabbbb... 꼴로 만드는 연산 횟수" 그러면 각 상태에서 투 포인터로 스.. [KOI] 백준 8983 - 사냥꾼 https://www.acmicpc.net/problem/8983 풀이 각 동물과 사대들의 거리를 생각해보자. 사대들과의 거리를 그래프 형태로 그리면 다음과 같은 형태가 나옴을 눈치챌 수 있다. 그래프의 형태는 유니모달 함수이며 우리는 삼분 탐색으로 닿을 수 있는 가장 짧은 사대를 찾을 수 있음을 알 수 있다. 사대의 좌표를 정렬한 후 입력받은 동물 좌표마다 삼분 탐색을 실시하여 피격당할 수 있는 동물의 마릿수를 구하면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 .. [KOI] 백준 2503 - 숫자 야구 https://www.acmicpc.net/problem/2503 체크리스트 서로 다른 숫자 세 개로 구성된 세 자릿수 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번 다른 자리에 위치하면 볼 한 번 풀이 수가 단 3자리에 1부터 9까지 이므로 3자리 숫자를 모두 검색하는 완전 탐색을 생각해볼 수 있다. 이때 "서로 다른 숫자 세 개"라는 조건에 유의하여 같은 숫자가 있으면 건너뛰도록 한다. 어떤 수 조합이 후보에 포함될 수 있으려면 N개의 질의에 대해 스트라이크와 볼 개수가 일치해야 한다. 하나라도 그렇지 않으면 모순이 발생한 것이므로 생각할 수 있는 조합이 될 수 없다. 모든 수 조합에 대해 N개의 질의를 만족하는 횟수를 구하면 정답을 받을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7.. 이전 1 2 3 다음
