백준 (223) 썸네일형 리스트형 백준 23280 - 엔토피아의 기억 강화 https://www.acmicpc.net/problem/23280 다음 점화식을 정의하자.$dp(i, j, k) := $ $i$번째 순서에서 왼손이 $j$, 오른손이 $k$에 있을 때 최적해번호는 총 12개가 있으므로 약 10001 × 12 × 12 크기의 메모리를 사용하여 동적 계획법을 시행할 수 있다.처음에 왼손과 오른손이 각각 번호 1, 3에 있다고 했으므로 $dp(0, 0, 2)$부터 메모이제이션을 하여 정답을 계산할 수 있다.정답 코드 - C++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#pragma GCC target("fm.. 백준 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)\] 으로만 보면 많은 연산이 필요할 것으로 보이나, 제한을 걸고 있기 때문에 안심하고 브루트포스를 해도 되는 것으로 이해할 수 있다. 문제의 제한을 이해했으므로 나머지는 신경 쓸 필요.. 백준 1069 - 집으로 https://www.acmicpc.net/problem/1069힌트더보기제목 그대로 집으로 가는 방법은 몇 개가 있을까? 넓은 관점으로 생각해본다.풀이더보기다음 그림을 보면 이 문제에 대한 핵심을 쉽게 이해할 수 있다. 위 그림을 보면 알 수 있듯이, 목표를 향해 일직선으로 가는 것보다 점프를 2번 해서 가는 방법이 더 빠른 경우가 존재할 수 있다. 우리는 이 사실을 반영하여 목표로 향하는 최소 시간을 구하기 위해 다음 두 방법을 섞었을 경우를 계산할 것이다. 1. 목적지까지 일직선으로 걷기 또는 점프하는 시간2. 목적지에 도착하기 위해 두 번 점프하는 시간 일단 초기해를 피타고라스의 정리로 계산한 두 지점 간의 일직선 거리 $(dx^{2} + dy^{2})^{\frac{1}{2}}$로 설정한다. 그.. 백준 27437 - 분수찾기 2 https://www.acmicpc.net/problem/27437힌트더보기문제에 그려진 테이블을 유심히 보자. 위와 같이 구분한다고 했을 때 패턴을 찾아낼 수 있는가?풀이더보기위 힌트에서 주어진 테이블을 대각선으로 나눴다. 그러면 우리는 각 대각선에서 발견할 수 있는 중요한 성질을 다음과 같이 정리할 수 있다. 각 대각선에 속한 수들의 집합을 $D_{1}, D_{2}, D_{3}, ...$으로 부르며 원소의 갯수는 $1, 2, 3, ...$이다. 이때 $D_{i}$의 원소인 $\frac{y}{x}$에서 $MAX(x, y) = i$이다. 우리는 $\sum_{i = 1}^{n}\nolimits i \leq X$를 만족하는 $i$의 최댓값을 파라메트릭 서치로 찾아낼 수 있다. 그리고 대각선을 문제의 규칙에.. 백준 32250 - Super Shy (Easy) https://www.acmicpc.net/problem/32250힌트 1더보기만약 먼저 앉은 사람이 아무도 없을 경우 아무 자리에나 앉을 수 있다. 이 조건이 대단히 중요하다.힌트 2더보기최초로 사람을 배치한 이후, 규칙에 따라 사람을 배치하는데 나타나는 성질을 찾을 수 있는가?풀이더보기먼저 사람을 아무 곳에 배치한다고 해보자. 그러면 그 사람을 기준으로 나눈 왼쪽 구간과 오른쪽 구간 $L$과 $R$을 얻을 수 있다. $L$과 $R$에서 사람을 배치할 때는 문제의 규칙에 의해 다음과 같은 성질을 발견할 수 있다. 구간 $L, R$에서 첫 번째 사람이 놓인 기준점을 포함하여 각 사람과의 거리는 2 또는 3이다. 이는 거리를 가능한한 멀리 떨어트려야 한다는 조건을 만족시키기 위해 중앙에 배치하면서 다시 두.. 이전 1 2 3 4 5 6 ··· 45 다음
