백준 (206) 썸네일형 리스트형 백준 1398 - 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.www.acmicpc.net 힌트 1더보기동전 교환 문제를 그리디 하게 풀려면 주어진 동전들의 값이 서로 서로소가 아니어야 함이 알려져 있다. 일단 적당한 범위 안에서의 답을 dp로 모두 구해놓고 dp로 도출한 해와 그리디로 푼 해의 차이를 비교해 보자. 유의미한 결과를 얻을 수 있는가?힌트 2더보기30, 40, 80, 90 해설더보기적당히 큰 범위 내에서 dp로 해를 찾은 뒤 그리디하게 구한 해와 비교해보자. 그러면 다.. 백준 2040 - 수 게임 https://www.acmicpc.net/problem/2040 이 문제는 대단히 교육적인 문제이므로 꼭 공부하는 것을 추천한다. 게임 전략 A와 B 둘 다 최적으로 플레이를 한다고 했다. 이를 수식으로 표현하면 어떻게 될까? A의 합을 $sum_{A}$, B의 합을 $sum_{B}$라고 하면 A와 B의 목표는 다음과 같이 정리할 수 있다. A는 $sum_{A} - sum_{B}$를 최소화시켜야 한다. B는 $sum_{A} - sum_{B}$를 최대화시켜야 한다. (혹은 $sum_{B} - sum_{A}$를 최소화시켜야 한다.) 그러면 저 값을 최적화 하는 문제로 표현할 수 있고 이는 동적 계획법으로 시도해볼 수 있을 것이다. 그런데 어떻게 동적 계획법을 해야 할까? 테이블을 다음과 같이 정의한다. d.. 백준 12986 - 화려한 마을 2 https://www.acmicpc.net/problem/12986 $O((N+Q)\sqrt N \log N)$ 솔루션 - Mo's + Indexed heap Mo's 알고리즘 적용을 위해 쿼리를 정렬한다. 그리고 -100000부터 100000까지의 값을 index로 취급하면 가장 많이 출연한 원소의 횟수를 indexed heap로 찾을 수 있다. 그러면 각 쿼리를 처리하면서 원소의 출연 횟수를 구역을 횡단할 때마다 $O(\log N)$의 시간 복잡도로 갱신하게 되고 쿼리의 답은 max indexed heap의 top이 된다. 시간 복잡도 : $O((N+Q)\sqrt N \log N)$ 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22.. 백준 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 https://www.acmicpc.net/problem/17353 사전 지식 imos법을 알면 풀이를 쉽게 이해할 수 있다. 이 포스트에서는 imos법을 알고 있다는 가정 하에 설명하도록 한다. 공차가 1인 등차 수열 이 문제는 공차가 1인 등차수열을 구간에 더하면서 포인트 쿼리를 수행한다. 여기서 포인트 쿼리를 구간 쿼리로 바꿔보자. 점 x에 떨어진 별의 개수가 아닌 구간 [1, x]의 합을 구하는 쿼리로 바꾼다. 왜 이렇게 쿼리를 바꾸냐면 쿼리 1을 스위핑 덧셈 문제로 바꾸기 위함이다. 얘를 들어 다음 배열을 살펴보자. 1 2 3 4 5 이 배열의 원소들 $a_{1}, a_{2},... $을 $imos(i) - imos(0)$의 형태로 구하려면 어떻게 할까? 1 1 1 1 1 -5 이렇게 배열을 구.. 백준 18287 - 체스판 이동 https://www.acmicpc.net/problem/18287 규칙 살펴보기 홀수 행와 짝수 행일 때의 이동은 그림으로 나타내면 다음과 같다. 문제에 아래로 가는 것만 가능하다 했으므로 다른 이동은 무시한다. 그러면 우리는 이 이동을 표현한 전이 행렬을 구상할 수 있다. MATRIX[i][j] := 현재 행의 i열에서 다음 행의 j열로 가는 경우의 수 그러면 $M^{2}$ 크기의 전이 행렬 두 개를 만들 수 있다. 이동 합성 행렬을 만든 건 좋은데 이 따로국밥인 행렬들을 어떻게 처리할지 난감하다. 이럴 때는 그냥 홀수 행 전이 행렬과 짝수 행 전이 행렬을 곱해 2번 이동하는 행렬을 만들면 된다. 그러면 우리는 2칸씩 이동하는 행렬을 표현했으므로 남은건 행렬 거듭제곱을 통해 이동 횟수 계산을 $O(M.. 이전 1 2 3 4 ··· 42 다음
